Формулы алгебры логики

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

Поставим в соответствие высказыванию P логическую переменную х, которая принимает значение 1, если Р истинно, 0, если Р ложно. Из логических переменных можно с помощью логических операций составлять различные конструкции, которые являются формулами алгебры логики.

Определение формулы:

а) любая логическая переменная является формулой;

б) если и формулы, то выражения , являются формулами;

в) никаких других формул, кроме построенных в а) и б) нет.

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

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

Т а б л и ц а 2.1.1

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

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

Пример 2.1.2 - Для формулы = таблица истинности имеет вид:

Т а б л и ц а 2.1.2

Введём новые важные логические операции, добавляя к пяти основным ещё три операции (тем самым расширим понятие логической формулы):

е) штрих Шеффера(антиконъюнкция). Обозначается .

По определению , или ;

ж) стрелка Пирса(антидизъюнкция). Обозначается .

По определению или ;

и) кольцевая сумма (логическое сложение, сложение по модулю два).

Обозначается . Определяется или .

Составим таблицы истинности этих операций, исходя из определений.

Т а б л и ц а 2.1.3

При тождественных преобразованиях, при составлении формул важно знать приоритеты операций (какая сильнее, какая слабее), как раскрывать скобки. Для этих целей приняты следующие соглашения:

а) внешние скобки не пишутся, например, вместо , будем писать ;

б) на множестве вводится транзитивное отношение

«>» - быть более сильным и отношение «~» - быть равносильным, по правилам, указанным на схеме:

Рисунок 2.1.1

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

Пример 2.1.3 –

а) в формуле скобки расставляются так: ;

б) в формуле скобки расставляются так: ;

в) в формуле скобки опустить нельзя, т.к. в силу наших соглашений выражению соответствует формула .

Дата добавления: 2014-12-27