Дополнение к курсу - математическая логика

Логика высказываний

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

Поэтому математическая логика строит искусственные точные языки. При этом часто используют термины «буква» и «слово». Фразы (или высказывания, или формулы) языка осуществляются как некоторые знаки, построенные по определенным правилам из элементарных знаков – знаков, частями которых в данном языке не интересуемся. Набор элементарных знаков языка называют алфавитом этого языка, а сами элементарные знаки – буквами этого языка. Под алфавитом понимают набор элементарных знаков.

В математической логике имеем дело с «высказываниями». Высказывания строят, высказывания и связи между ними изучают.

Определение 1.1. Высказывание – это предложение, которое может принимать два значения: истина (И) или ложь (Л) (или соответственно, 1, 0). Таким образом, о высказывании можно сказать, что оно имеет логическое значение.

В языке арифметики имеются высказывания, о которых нельзя сказать истинны они или ложны. Таковы, например, следующие высказывания:

1. Существует нечетное совершенное число.

2. Существуют положительные натуральные числа k, l, m и n, такие, что kⁿ⁺²+lⁿ⁺²=mⁿ⁺².

3. Каково бы ни было натуральное число p, существует простое число q, большее p и такое, что число q+2 также простое.

4. Всякое четное число есть сумма двух простых чисел.

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

Определение 1.2. Пропозициональные переменные – это буквы (символы), которые посредством подстановки можно замещать любыми высказываниями. Например, p,q,r,p₁,q₂,r₂… Иными словами, пропозициональные переменные есть буквы, пробегающие множество высказываний.

Определение 1.3. Формулы логики высказываний – это правильно построенные выражения из пропозициональных переменных и знаков логических операций (Ø,Ù,Ú,Þ,Û), а также скобок и запятых.

Далее рассмотрим следующий алфавит, имеющий в своем составе: 1) пропозициональные переменные, 2) знаки логических операций (Ø,Ù,Ú,Þ,Û), 3) технические знаки (), ,.

Определение 1.4. Словом будем называть любую последовательность символов указанного алфавита. Например, (ÙÞØpqÛ) – есть слово, ((pÙq)Þ(Ør)) – также слово.

Теперь можно сформулировать следующее правило:

Определение 1.5. Слово F называется правильно построенным, если существует такая конечная последовательность слов F₁,F₂,…,F_n, в которой последнее слово совпадает с F (F_n=F) и выполняются следующие условия: каждый член этой последовательности F_i (i=1,…,n) есть либо 1) пропозициональная переменная, либо 2) отрицание слова, ранее встретившегося в этой последовательности, либо 3) конъюнкция или дизъюнкция или эквивалентность двух слов, ранее встречавшихся в этой последовательности.

Например, ((pÙq)Þ(Ør)) – это правильно построенное слово (так как выполнены условия 1),2),3) сформулированного выше правила).

Введем кванторы: " и $, где " - всеобщность (генерализация), «для всех», $ - существование (экзистенция), «существует».

При построении формул используются символы, которые называются логическими символами. Они делятся на две категории: логические связки и кванторы.

Семантика формул определяется их свойством быть истинными или ложными, то есть принимать значение 1 (T, true) - истина, или 1 (F, false) - ложь.

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

Дизъюнкция и конъюнкция связывают сильнее, чем импликация, а сами равноправны в отношении связывания. То есть можно сказать, что скобки могут использоваться для указания порядка выполнения операций и опускаются с учетом принятого старшинства операций: Ø, &, Ú, ®, «. Аналогично, равноправны кванторы; они связывают сильнее, чем логические связки.

Определение 1.6. Интерпретация, при которой формула принимает значение Т, называется моделью этой формулы.

Определение 1.7. Формула выполнима (непротиворечива), если она допускает хотя бы одну модель, т.е. ее можно интерпретировать со значением Т. Например, формула р&q является выполнимой.

Определение 1.8. Формула невыполнима (противоречива, тождественно ложна), если она не имеет ни одной модели, то есть при всех интерпретациях является ложной. Например, формула (р&Øр) невыполнима.

Таблица логических простых функций

p	q	Øp	p&q (pÙq)	pÚq	pÞq (p®q)	pÛq (pºq)	p¯q	p½q	pÅq
1	1	0	1	1	1	1	0	0	0
1	0	0	0	1	1	0	0	1	1
0	1	1	0	1	0	0	0	1	1
0	0	1	0	0	1	1	1	1	0
		Отри- цание	Конъюнкция	Дизъюнкция	Импли- кация	Эквива лентность	Стрелка Пирса	Штрих Шеффера	Сложение по модулю 2

Табличная проверка формул логики высказываний производится следующими способам:

1. Подстановка вместо символов имен высказываний и проверка формулы при всех значениях этих высказываний. Число проверок равно N=2ⁿ, где n – число высказываний (булевых переменных).

2. То же, что и п.1., только подстановка вместо символов всех возможных значений истинности («1» или «0» и исчисление значения формулы в соответствии с таблицей истинности логических простых функций).

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

Так можно сформулировать следующие правила:

1. Отрицание истинного высказывания ложно, а отрицание ложного высказывания истинно.

2. Операция дизъюнкция: в латыни ей соответствует союз «vel», в связи с чем для нее и принято обозначение «»; в русском языке ей соответствует союз «или».

Дизъюнкция ложна в единственном случае: когда оба ее члена ложны.

Например, рассмотрим высказывание x₃=x₁x₂, где x₁=aA, x₂=aB, А и В – произвольные множества. x₃ истинно тогда и только тогда, когда элемент а принадлежит объединению множеств А и В.

3. Операция разделительная дизъюнкция, исключающее «или» или сложение по модулю два. Из таблицы видно, что она принимает значение «истина» тогда и только тогда, когда или один, или другой из операндов истинны, но не оба имеют одно и то же значение истинности. В латыни есть союз «aut» для разделительной дизъюнкции, в русском языке это союз «или… или». Операция обозначается символом «».

Например, пусть x₁=aA, x₂=bB, А и В – произвольные множества, и x₃=x₁x₂. В этом случае x₃ примет значение «истина» исключительно на симметрической разности множеств A и B.

4. Конъюнкция (или логическое умножение) истинна в единственном случае: когда оба ее члена истинны.

5. Операция – импликация, ей соответствует обозначение «» или «», или «»; смысл английского слова «implication» означает «подразумеваемое». Импликация ложна в единственном случае: когда ее условие истинно, а заключение ложно. Таким образом, в математике конструкция «если А, то В» ложна тогда и только тогда, когда из истины следует ложь.

6. Эквивалентность истинна, когда ее правые и левые части имеют одинаковое логическое значение.

7. Операция стрелка Пирса обозначается символом «» и принимает значение «истина» тогда и только тогда, когда оба ее операнда ложны.

8. Операция штрих Шеффера, обозначаемая символом «|». Ее истинностное значение утверждает, что «кто-то лжет»; высказывание, определенное либо первым, либо вторым из двух операндов данной операции, ложно.

Пример. Построить таблицу истинности для формулы ØPÞQÙR.

Решение. Для удобства запишем ее в виде: (ØP)Þ(QÙR). Теперь построим таблицу истинности.

P	Q	R	ØP	QÙP	ØPÞQÙR
1	1	1	0	1	1
1	1	0	0	0	1
1	0	1	0	0	1
1	0	0	0	0	1
0	1	1	1	1	1
0	1	0	1	0	0
0	0	1	1	0	0
0	0	0	1	0	0

Определение 1.9. Формула  общезначима (является тавтологией), если она истинна в любой интерпретации. Например, формула (рÚØр) общезначима.

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