Булевы функции. Всякую формулу логики высказываний можно рассматривать как некоторую функцию: каждая буква (высказывание) может принимать одно из двух значений

Всякую формулу логики высказываний можно рассматривать как некоторую функцию: каждая буква (высказывание) может принимать одно из двух значений "истина" или "ложь", при этом сложное высказывание, заданное этой формулой, также может быть истинным или ложным. Так, формула: ((x ® y) º )Ú(z× y) = f (x,y,z) выражает функцию от переменных x, y и z.

Такого рода функции называются булевыми, а их аргументы – булевыми переменными.

Функции называются тождественно истинными (тавтологии), если при любых значениях переменных, значение функции – истинно.

Пример 1. (x Ú ); x ® (y ® x); (x × ) ® (x × y).

Функции называются тождественно ложными, если при любых значениях переменных, значение функции – ложно.

Пример 2. (x × ); (x ® (y ® x)) º (y × ).

Функции называются равносильными, если их значения при любом наборе значений, входящих в них переменных совпадают.

Пример 3. f = (x º y) ® (x × z) и g = ((x × ) Ú (× y)) Ú (x × z).

Составление таблиц истинности.

Таблица истинности логической формулы выражает соответствие между всевозможными наборами значений переменных и значениями формулы. Количество наборов для формулы – 2 ⁿ (n – количество переменных). Удобной формой записи при нахождении значений формулы является таблица, содержащая кроме значений переменных и значений формулы также и значения промежуточных формул.

Пример 4. Таблица истинности для формулы:

Переменные	Промежуточные логические формулы	Формула
х	y	z

Постройте таблицы истинности для примеров 1-3.

Дата добавления: 2014-01-11