Формулы. Булевы функции

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

Правила построения пропозициональных формул (п.ф.) таковы:

1) каждая пропозициональная переменная есть формула, которая называется элементарной или атомарной;

2) если и - пропозициональные формулы, то - также пропозициональные формулы;

3) любая формула имеет вид, указанный в 1 или 2.

Соглашение о порядке выполнения логических операций остается в силе. Кроме того, иногда внешние скобки опускаются.

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

Если считать, что значениями пропозициональных переменных являются не высказывания, а их истинностные значения И и Л, то такие переменные называются булевыми. Сами буквы И и Л называются булевыми константами (часто они обозначаются соответственно через I и O), а упорядоченные -ки булевых констант – булевыми -мерными векторами. Тогда каждой формуле можно сопоставить функцию , у которой каждый аргумент одно из двух значений И или Л, либо I или O, и сама функция принимает одно из этих двух значений. Такая функция называется булевой. Итак, каждая булева функция от переменных сопоставляет каждому -мерному булеву вектору булеву константу . Каждая формула логики высказываний порождает булеву функцию, значение которой находится так, как указано в п. 2.2.

Определение истинностного значения удобно свести в таблицу (называемую также таблицей истинности). Например, найти значения .

А	В
и	и	и	л	л	л	л
и	л	и	л	л	л	л
л	и	и	и	и	и	и
л	л	л	и	л	и	л

Обращаем особое внимание студентов на первый этап – перебор возможных значений, приписываемых пропозициональным переменным. Ясно, что столбцы, отвечающие их одинаковым значениям, должны быть одинаковыми. Если переменные расположить в алфавитном порядке (а для одинаковых букв с индексами – по возрастанию индексов), то для одной, двух, трех переменных перебор производить в следующем порядке:

и		и	и		и	и	и
л		и	л		и	и	л
		л	и		и	л	и
		л	л		и	л	л
					л	и	и
					л	и	л
					л	л	и
					л	л	л

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

В некоторых книгах, например в [2], столбец из И и Л пристраивается к удвоенной таблице не слева, а справа. Если в пропозициональной формуле имеется n различных букв, то в таблице будет строк, соответствующих всем возможным распределениям истинностных значений пропозициональных букв.

Тавтологии

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

Следует подчеркнуть, что изучением смысла простых высказываний логика не занимается, это дело тех конкретных наук, к которым эти высказывания относятся. Логика же определяет значение сложных высказываний в зависимости от значений простых, т.е. исследует зависимость истинностных значений сложных высказываний от истинностных значений простых.

Пример 1. Выяснить, является ли тавтологией формула . Для этого построим таблицу истинности:

А	В
и	и	и	и	и	и
и	л	л	л	л	и
л	и	л	и	л	л
л	л	и	Л	и	л

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

Пример 2. Выяснить, является ли тавтологией формула ? Построим истинностную таблицу

А	В	С
и	и	и	и	и	и	и	и
и	и	л	и	л	л	л	и
и	л	и	л	и	л	и	и
и	л	л	л	и	л	л	и
л	и	и	и	и	и	и	и
л	и	л	и	л	л	и	и
л	л	и	и	и	и	и	и
л	л	л	и	и	и	и	и

Таким образом, рассматриваемая формула является тавтологией.

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

Теорема (правило modus ponens (MP) для тавтологий). Если и , то .

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

Дата добавления: 2015-11-14