П.1.3. Формулы алгебры высказываний

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

Определение:

1. Любое высказывание (высказывательная переменная) – формула.

2. Если А и В формулы, то - тоже формулы.

При построении формулы используют скобки (...). Условимся внешние скобки опускать, к примеру, формулу будем записывать . Существуют и другие правила, позволяющие не ставить лишние скобки. Например, конъюнкция выполняется первой, дизъюнкция – второй, импликация и эквиваленция равноправны и выполняются последними. Каждой формуле при заданных значениях входящих в нее переменных приписывается одно из двух значений 0 или 1. Для формул составляется таблица истинности. Если формула состоит из n- элементов, то ее таблица истинности содержит 2ⁿ строк. Приписывание значений истинности или ложности высказываниям, входящим в формулу, называется интерпретацией этих высказываний. Под интерпретацией формулы понимается приписывание значений истинности высказываниям, входящим в эту формулу.

Пример 11. Составить таблицу для формулы

Решение:

x	y	x→y

Все формулы алгебры логики делятся на три класса: 1. Тавтология.

2.Тождественно ложные. 3. Выполнимые.

Определение 1.1. Формула А называется тавтологией (или тождественно ис-тинной), если та истина при всех значениях высказывательных переменных, входящих в эту формулу.

Определение 1.2. Формула А называется тождественно ложной, если она ложна при всех значениях высказывательных переменных, входящих в эту формулу.

Определение 1.3. Формула А называется выполнимой, если она принимает значение единицы, хотя бы на одном наборе, входящих в нее переменных и не является тождественно истинной.

Пример 12. Рассмотрим формулу

Построим таблицу истинности этой формулы

x	y	x→y

Анализируя столбец последний убеждаемся, что формула А является тавтологией.

Пример 13. Показать выполнимость формулы

Построим таблицу истинности

x	y	x→y	y→x	B

Анализируя столбец значений истинности формулы В, убеждаемся, что формула В является выполнимой.

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