Теоретические сведения. Формулы алгебры логики будем обозначать больши­ми латинскими буквами

Формулы алгебры логики будем обозначать больши­ми латинскими буквами.

Логические значения форму­лы при различных комбинациях значений входящих в нее высказываний можно описать посредством таблицы, которая называется таблицей истинности формулы.

Формула А называется тождественно истинной (или тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных.

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

Логические функции, таблица истинности которых при некоторых значениях переменных значение X истинно, а при некоторых — ложно называют вычислимыми.

Если у двух логических функций совпадают таблицы истинности, то есть на всех наборах значений входных переменных они принимают одинаковое значение, то их называют равносильными или эквивалентными. Это обозначается знаком º.

Пример. Составим таблицу истинности для формулы , которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце — значение формулы. В результате получим таблицу:

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

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1, то есть является тождественно истинной (или тавтологией).

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

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 0, то есть является тождественно ложной.

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

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

Из таблицы видно, что формула в некоторых случаях принимает значение 1, а в некоторых — 0, то есть является выполнимой.

Пример 1. Из простых высказываний:

“Виктор хороший пловец” - А;

“Виктор хорошо ныряет” - В;

“Виктор хорошо поет” - С,

составлено сложное высказывание, формула которого имеет вид: X=(AÚC)Ù(AÚB).

Установить, эквивалентно ли высказывание Х высказыванию: “Виктор - хороший пловец и Виктор хорошо поет”.

Решение. Y=AÙC

А	В	С	AÚC	AÚB	X	Y=AÙC

Вывод. Высказывание X не эквивалентно высказыванию Y.

Упражнение 1. Установить является ли данное высказывание тавтологией.

A	B	AÙB

Вывод. Высказывание является тавтологией.

Упражнение 2. Установить истинность высказываний:

а) ((X1®X2)®X3)Ù(X3«X1)

			F1	F2	F3
X1	X2	X3	X1®X2	F1®X3	X3«X1	F2ÙF3
1	0	1	0	1	1	1
1	1	1	1	1	1	1

Вывод. Высказывание ((X1®X2)®X3)Ù(X3«X1) истинно, когда:

1) X1º1; X2º0; X3º0; 2) X1º1; X2º1; X3º1

б) ((X®Y)Ù(Y®Z))®(X®Z)

			F1	F2	F3	F4
X	Y	Z	X®Y	Y®Z	F1ÙF2	X®Z	F3®F4

Вывод. Высказывание ((X®Y)Ù(Y®Z))®(X®Z) истинно всегда.

Задание №1. Даны простые высказывания:

А = {Принтер – устройство ввода информации},

В = {Процессор – устройство обработки информации},

С = {Монитор – устройство хранения информации},

D = {Клавиатура – устройство ввода информации}.

Определите истинность составных высказываний:

а) (А & В) & (C Ú D);б) (А & В) Þ (C Ú D);

в)(А Ú В) Û (C & D);г) Û .

Задание №2. Составьте таблицы истинности для следующих формул логики высказываний:

а) A & (A Ú B Ú C);

б) B Ú (B & A);

в)

г) B & (A Ú C).

Задание №3. Составив соответствующие таблицы истинности, докажи­те, что все следующие формулы являются тавтологиями:

Задание №4. Составьте таблицы истинности для следующих высказываний:

а)

б)

в)