Тема 2.5 Равносильные формулы. Свойства.

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

Основы равносильности:

1. Коммутативность.

а) (для конъюнкции);

б) (для дизъюнкции).

2. Ассоциативность.

а) (для конъюнкции);

б) (для дизъюнкции).

3. Дистрибутивность.

а) (для конъюнкции относительно дизъюнкции);

б) (для дизъюнкции относительно конъюнкции).

4. Закон де Моргана.

а) ^{┐ ┐ ┐} (отрицание конъюнкции есть дизъюнкция отрицаний);

б) ^{┐ ┐ ┐} (отрицание дизъюнкции есть конъюнкция отрицаний).

5. Идемпотентность.

а) (для конъюнкции);

б) (для дизъюнкции).

6. Поглощение.

.

^┐

7. Расщепление (склеивание).

а) (1–ый закон расщепления);

б) (2–ой закон расщепления).

8. Двойное отрицание.

^┐┐х=х

9. Свойства констант.

а)

б)

в)

г)

д)

е) .

10. Закон противоречия.

11. Закон “исключенного третьего”.

Каждая из перечисленных равносильностей может быть доказана с помощью таблиц значений функций, составленных для выражений, стоящих слева и справа от символа “ ”. Докажем, например, равносильность 4а. Для этого составим таблицу.

Таблица

х	у					
0 0 1 1	0 1 0 1	0 0 0 1	1 1 1 0	1 1 0 0	1 0 1 0	1 1 1 0

Из таблицы видно, что  , что и требовалось доказать.

Тест

1. Следующее высказывание может быть интерпретировано как сложное высказывание: "Неверно, что первым пришел Петр или Павел". Каковы составляющие его элементарные высказывания?

а) А: "Неверно, что первым пришел Петр"; В: "Неверно, что первым пришел Павел";

б) А: "Первым пришел Петр"; В: "Неверно, что первым пришел Павел";

в) А: "Первым пришел Петр"; В: "Первым пришел Павел".

2. Какой из формул может быть записано высказывание предыдущего вопроса?

а) А ∨ В;

б) А ∨ В;

в) А ∧В.

3. Будет ли высказывание S=(А→В)∧(В→С)→(А→С):

а) тождественно истинным;

б) тождественно ложным;

в) переменным.

4. В высказывании S: "Треугольники равны только тогда, когда равны

их стороны". Равенство углов в треугольнике является:

а) необходимым условием;

б) достаточным условием;

в) необходимым и достаточным условием.

Самостоятельная работа №3.

Самостоятельная работа №4.

Контрольная работа

I вариант

1. Составить истинностную таблицу для ы:

2. Записать приведённую равносильную форму для ы:

3. Является ли заданная высказывательная форма тавтологией:

4. Составить ДНФ и КНФ для ы:

5. Упростить:

6. Выразить заданную функцию F из алгебраического высказывания через F₁(x)=¬ x; F₂(x,y)=x y; F₃(x,y)=x y

F=(x∧y∧z)∨(¬x→y)

II вариант

1. Составить истинностную таблицу для ы:

2. Записать приведённую равносильную форму для ы:

3. Является ли заданная высказывательная форма тавтологией:

4. Составить ДНФ и КНФ для ы:

5. Упростить:

6. Выразить заданную функцию F из алгебраического высказывания через F₁(x)=¬ x; F₂(x,y)=x y; F₃(x,y)=x y

F=(¬y→¬x)∧(x∨¬y∨¬z)