2018-02-13
4067
Цель работы: научиться составлять таблицы истинности формул алгебры высказываний и упрощать формулы алгебры высказываний.
Ход выполнения работы:
1. Изучить теоретический материал.
2. Получить задание у преподавателя.
3. Выполнить задание.
4. Ответить на контрольные вопросы.
5. Защитить выполненное задание.
Краткие теоретические сведения
Пропозициональная переменная – переменна, вместо которой можно подставлять высказывания.
Формула алгебры высказываний определяется следующим образом:
1. Каждая отдельно взятая пропозициональная переменная – формула алгебры высказываний.
2. Если F и G – формулы алгебры высказываний, то выражения 
также являются формулами алгебры высказываний.
3. Никаких других формул алгебры высказываний нет.
Для каждой формулы должна существовать конечная последовательность всех ее подформул (конечная последовательность, которая начинается с входящих в данную формулу пропозициональных переменных, заканчивается самой этой формулой, и каждый член этой последовательности, не являющийся пропозициональной переменной, является либо отрицанием уже имеющегося члена этой последовательности, либо получается из двух уже имеющихся членов этой последовательности их соединением с помощью одного из знаков 
и заключением полученного выражения в скобки.
Такую последовательность всех подформул данной формулы является порождающей последовательностью для данной формулы.
Если формула содержит n пропозициональных переменных, то первые n столбцов и последний столбец составленной таблицы задают соответствия между логическими значениями исходных высказываний и логическим значением составного высказывания, получаемого по данной формуле. Эти столбцы образуют таблицу истинности данной формулы.
При этом остальные столбцы, в которых представлены логические значения формул, образующих порождающую последовательность для данной формулы, носят вспомогательный характер.
Также можно отметить, что число наборов значений n пропозициональных переменных равно 2 n.
Формулы могут относиться к одному из классов:
1) общезначимые (последний столбец таблицы истинности такой формулы содержит и 0, и 1)
2) тавтологии (последний столбец истинности такой формулы состоит только из 1)
3) противоречия (последний столбец истинности такой формулы состоит только из 0)
Формулы алгебры высказываний F и H равносильны, если они принимают одинаковые логические значения на любом наборе значений входящих в них высказываний.
Одну равносильную формулу можно получить из другой, используя следующие равносильные преобразования
I. Основные равносильности:
II.Равносильности,выражающиеоднилогическиеоперации черездругие:
III. Равносильности, выражающие основные законы алгебры логики:
1) 
коммутативность конъюнкции
2) 
коммутативность дизъюнкции
3) 
ассоциативность конъюнкции
4) 
ассоциативность дизъюнкции
5) 
дистрибутивность конъюнкции
6) 
дистрибутивность дизъюнкции
Образец выполнения
1. Составить таблицу истинности формулы и определить вид формулы (общезначимая, тождественно истинная (тавтология), тождественно ложная (противоречие)):
Решение
Составим таблицу истинности формулы. Формула F зависит от двух переменных P и Q, поэтому таблица истинности будет содержать 4 строки
| P | Q | P®Q | (P®Q)®P | F =
|
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Так как в последнем столбце таблицы истинности присутствуют и 0, и 1, то формула является общезначимой.
2.Доказать, что формула является тавтологией (упростив формулу):
Решение
Преобразуем формулу, используя основные равносильные преобразования
Отсюда получаем, что формула является тавтологией.
3. Преобразовать формулу равносильным образом так, чтобы она содержала только операции дизъюнкции, конъюнкции и отрицания:
Решение
Преобразуем формулу, используя основные равносильные преобразования
Получена формула, содержащая только операции отрицания, конъюнкции и дизъюнкции. Таким образом,
Задания:
1. Составить таблицу истинности формулы и определить вид формулы (общезначимая, тождественно истинная (тавтология), тождественно ложная (противоречие)):
1) 
2) 
3) 
4) 
5) 
6) 
7) 
8) 
9) 
2.Доказать, что формула является тавтологией (упростив формулу):
1) 
2) 
3) 
4) 
5) 
6) 
7) 
8) 
9) 
3. Преобразовать формулу равносильным образом так, чтобы она содержала только операции дизъюнкции, конъюнкции и отрицания:
1) 
2) 
3) 
4) 
5) 
6) 
7) 
8) 
9) 
Контрольные вопросы
1. Что такое формула алгебры высказываний
2. Что такое порождающая последовательность формулы
3. Что представляет собой таблица истинности формулы
4. Какие классы формул Вам известны
5. Какие формулы называются равносильными.
6. Перечислить основные группы равносильных преобразований
