Высказывания | Предикаты | Логические функции

ВЫСКАЗЫВАНИЕМ называется повествовательное предложение, которое может быть истинным или ложным. Например, «сегодня хорошая погода». Если любая часть предложения бессмысленна (то есть нельзя сказать, она истинна или ложна), то говорят, что ВЫСКАЗЫВАНИЕ ПРОСТОЕ. Предыдущее предложение именно такое.

Обычно в предложении можно выделить части, сами являющиеся высказываниями, которые соединены союзами «и», «или», «иначе», «если…то…» и т.п. Однако разбиение сложного повествовательного предложения на простые высказывания нужно делать по смыслу, а не по словам. В предложении «в этой аудитории присутствуют студенты и преподаватель» частями-высказываниями являются
(в этой аудитории присутствуют студенты), (в этой аудитории присутствует преподаватель), которые соединены союзом и:
Смысл союза И таков, что значением сложного высказывания будет истина, если истинны оба входящие в него простые высказывания, и ложь, если хотя бы одно простое высказывание ложно. Неправильная форма: (в аудитории присутствуют студенты) и (преподаватель). Здесь вторая скобка не является высказыванием, поскольку она не может быть истинной или ложной.

Правил преобразования сложного предложения в набор простых высказываний, соединенных союзами, не существует. Эта трудность присуща всем естественным языкам, и она сильно затрудняет, в частности, перевод с одного языка на другой. Однако такое преобразование в большинстве случаев легко осуществляет любой человек, владеющий языком. ПРАВИЛО: в сложном высказывании союзы должны стоять только между высказываниями!

Если высказывание содержит переменные, то оно называется логическим выражением или ПРЕДИКАТОМ. Например, (х больше 0). Логическое выражение (предикат) может быть истинным или ложным в зависимости от значения переменной х. Другими словами, предикат – функция от переменных, которая принимает только два значения – {истина, ложь}. Для предикатов используют функциональные обозначения: M(x) = (x>0).

Предикаты позволяют формализовать СВОЙСТВА ПЕРЕМЕННЫХ: M(x) = true означает, что x обладает свойством (x>0), а M(x) = false означает, что х не обладает свойством (x>0).

На Паскале можно написать программу для вычисления значений этого предиката:

function M(x: real):boolean;            int M(float x);
begin M:= (x>0) end;             { if (x>0) return 1;
  else return ; }

БУЛЕВОЙ ПЕРЕМЕННОЙ называется переменная, принимающая значения {истина, ложь}.
БУЛЕВОЙ ФУНКЦИЕЙ называют предикат, у которого переменные булевы.

Такой функцией, например, является сложное высказывание (в аудитории присутствуют студенты) и (в аудитории присутствует преподаватель), в котором первая и вторая скобки рассматриваются как переменные.

Можно также сказать, что булева функция – функция от переменных, принимающих два значения, и множество ее значений состоит из двух элементов. Обычно эти два значения обозначаются либо {0, 1}, либо {false, true}. Обычно обозначение {0, 1} выбирают, если нет опасности смешать логическую истину с числом 1. Если же в тексте употребляются как числа, так и логические значения, то выбирают второе обозначение.

В Паскале есть две логические константы false, true и тип Boolean = {false, true}, с помощью которого можно вводить логические переменные: var x,y: Boolean;

В логике используются союзы И, ИЛИ, НЕТ, ЛИБО…ЛИБО, ЕСЛИ…, ТО…
Смысл этих союзов обычный:

1. А ИЛИ В истинно, если истинно А или истинно В,
2. НЕТ А истинно, если А ложно,
3. ЛИБО А, ЛИБО В истинно, если истинно А или В, но не оба сразу,
4. ЕСЛИ А, ТО В ложно, если истинно А и ложно В. Во всех остальных случаях это  выражение истинно. Например, ЕСЛИ ложь, ТО В истинно не зависимо от В. Говорят в    связи с этом, что из лжи следует что угодно.

Союзам И, ИЛИ, НЕТ, ЛИБО…ЛИБО в Паскале соответствуют булевы операторы: and, or, not, xor – «и», «или», «не», «разделительное или». Оператор and называется также КОНЪЮНКЦИЕЙ, оператор or – ДИЗЪЮНКЦИЕЙ, оператор not - ОТРИЦАНИЕМ. Выражения вида (x or y),  (x and y), ((x and not(y)) or (not(x) and y)),и т.п. – называются булевыми.
Каждое булево выражение задает булеву функцию. Мы увидим, что верно и обратное: каждая булева функция может быть задана булевым выражением.

Функция f, зависящая от п переменных x1, x2,…, xnназывается булевой, или переключательной, если функция f и любой из ее аргументов  операторы: and, or, not, xor – «и», «или», «не», «разделительное или». Оператор and называется также КОНЪЮНКЦИЕЙ, оператор or – ДИЗЪЮНКЦИЕЙ, оператор not - ОТРИЦАНИЕМ. Выражения вида (x or y),  (x and y), ((x and not(y)) or (not(x) and y)),и т.п. – называются булевыми.

Каждое булево выражение задает булеву функцию. Мы увидим, что верно и обратное: каждая булева функция может быть задана булевым выражением.

Функция f, зависящая от п переменных x1, x2,…, xnназывается булевой, или переключательной, если функция f и любой из ее аргументов  принимают значения только из множества {0, 1}. Аргументы булевой функции также называются булевыми.
Наиболее распространенными способами задания булевых функций являются: табличный, метод перечислений, цифровой эквивалент, аналитический, семантическое дерево.

При табличном способе булева функция f(x1,…, xn) задается таблицей истинности (табл. 1.1), в левой части которой представлены все возможные двоичные наборы длины п, а в правой указывается значение функции на этих наборах.

Таблица  1.1 – Таблица истинности функции f1

Вернуться в оглавление:Цифровые автоматы