ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

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

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

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

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

2. 1.1. Высказывания. Логические связки

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

Высказывания чаще всего обозначают маленькими латинскими буквами a, b, c, х₁, х₂, …

В логике высказываний интересуются не содержанием, а истинностью или ложностью высказываний. Истинностные значения – истина и ложь – будем обозначать И и Л соответственно. Множество {И, Л} называется множеством истинностных значений.

Определение. Высказывание называют простым (элементарным), если оно рассматривается как некое неделимое целое (аналогично элементу множества). Сложным (составным) называется высказывание, составленное из простых с помощью логических связок.

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

№ набора	a
0	0	1
1	1	0

Определение. Отрицанием высказывания является новое высказывание, истинное только тогда, когда исходное высказывание ложно (табл. 3).

Отрицание обозначается через и читается как «не а», «неверно, что а».

Пример 15.

А – «Степан любит танцевать».

Определение. Конъюнкцией двух высказываний является новое высказывание, которое истинно только тогда, когда оба исходных высказывания истинны (табл. 4).

Конъюнкция обозначается или a&b и читается как «a и b», «a, но b», «a, а b».

Пример 16.

а – «Степан любит танцевать», b – «Степан любит петь».

Тогда - «Степан любит танцевать и петь».

Дизъюнкция обозначается через и читается как «a или b».

Пример 17.

а – «Степан любит танцевать», b – «Степан любит петь».

Тогда - «Степан любит танцевать или петь».

Импликация обозначается a® b и читается как «если a, то b»; « из а следует b». При этом a называется посылкой или условием, b – следствием или заключением.

Пример 18.

а – «Степан любит танцевать», b – «Степан любит петь».

Тогда - «Если Степан любит танцевать, то он любит петь».

Эквивалентность обозначается a» b и читается как «a эквивалентно b».

Пример 19.

а – «Степан любит танцевать», b – «Степан любит петь».

Тогда - «Для того, чтобы Степан любил танцевать, необходимо и достаточно, чтобы он любил петь».

Сведем все сказанное выше в единую таблицу и введем в рассмотрение еще три операции: сумма по модулю два, штрих Шеффера, стрелка Пирса (табл. 8).

Таблица 8

2.1.2. Формулы логики высказываний

Определим понятие формулы логики высказываний.

Определение. Алфавитом называется любое непустое множество. Элементы этого множества называются символами данного алфавита. Словом в данном алфавите называется произвольная конечная последовательность символов (возможно пустая).

Алфавит логики высказываний содержит следующие символы:

· высказывательные переменные;

· логические символы;

· символы скобок.

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

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

2) если А и В – формулы, то Ø А, А Ù В, АÚ В, А® В, АÅ В, А »В, А ï В, А ¯ В – формулы;

3) только те слова являются формулами, для которых это следует из 1) и 2).

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

Пример 20.

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

1. «Сегодня понедельник или вторник».
2. «Идет снег или дождь».
3. «Если идет дождь, то крыши мокрые. Дождя нет, а крыши мокрые».
4. «Что в лоб, что по лбу».

Решение.

1. Составное (сложное) высказывание «Сегодня понедельник или вторник» состоит из двух простых:

ü а – «сегодня понедельник»;

ü b – «сегодня вторник».

Высказывания а и b соединены связкой «или» очевидно в разделительном смысле (не допускается одновременное выполнение обоих условий), то есть используется логическая связка «сумма по модулю два». Таким образом, данное высказывание представимо логической формулой: a Å b.

2. Высказывание «Идет снег или дождь» также состоит из двух простых, соединенных связкой «или»:

ü а – «идет снег»;

ü b – «идет дождь».

Но в отличие от предыдущего связка «или» использована здесь не в разделительном смысле, поэтому – используется логическая связка дизъюнкция и логическая формула имеет вид: аÚb.

3. Сложное высказывание «Если идет дождь, то крыши мокрые. Дождя нет, а крыши мокрые» включает два простых высказывания:

ü а – «идет дождь»;

ü b – «крыши мокрые».

В первом предложении «Если идет дождь, то крыши мокрые» высказывания а, b соединены связкой «если …, то…»: а ® b.

Во втором «Дождя нет, а крыши мокрые» союз «а» здесь имеет смысл связки «и» (Ù), и кроме того высказывание а следует взять с отрицанием: .

Остается объединить представленные выше два высказывания в одно связкой Ù:

.

4. Высказывание «Что в лоб, что по лбу», если обозначить:

ü а – «в лоб»,

ü b – «по лбу»,

представимо логической формулой a » b.

Пример 21.

Представить логической формулой следующий текст:

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

Введем обозначения простых высказываний, содержащихся в первом предложении:

A – «фирма продолжает выпуск существующего продукта»;

B – «фирма ориентирована на существующий рынок;

C – «для фирмы целесообразна (привлекательна) стратегия «малого корабля»;

D – «для фирмы целесообразна (привлекательна) стратегия экономии издержек»;

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

(AÙB)®(С~D).

Второе предложение содержит новые простые высказывания:

K – «интенсивный маркетинг является стратегическим хозяйственным фактором организации»;

L – «интенсивный маркетинг является слабой стороной организации».

Логическая формула, представляющая второе предложение:

(KÙL)®(C~D).

В третьем предложении содержатся новые простые высказывания:

М – «интенсивный маркетинг является сильной стороной организации»;

N – «фирме следует придерживаться стратегии захвата новых рынков для существующего продукта».

Логическая формула для третьего предложения:

(KÙM)®N.

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

((AÙB)®(С~D))Ù( (KÙL)®(C~D))Ù( (KÙM)®N).

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

Определение. Формула называется выполнимой (опровержимой), если существует такой набор значений переменных, при которых эта формула принимает значение 1 (0).

Определение. Формула называется тождественно-истинной, или тавтологией (тождественно-ложной или противоречием), если эта формула принимает значение 1 (0) при всех наборах значений переменных.

Пример 22.

Составить таблицы истинности для формул:

1. ;

2. .

Решение.

1. Таблица истинности для формулы имеет вид (табл. 9):

Таблица 9

1. Таблица истинности для формулы имеет вид (табл. 10):

Таблица 10

№	x	y	z

2.1.3. Равносильность формул логики высказываний

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

Рассмотрим основные равносильности логики высказываний.

Пусть А, В, С – произвольные формулы. Тогда справедливы следующие свойства логических операций (табл. 11):

Таблица 11

1. Идемпотентность
А Ù А = А	А Ú А = А
2. Коммутативность
А Ù В = В Ù А	А Ú В = В Ú А
3. Ассоциативность
А Ù (В Ù С) = (А Ù В) Ù С	А Ú (В Ú С) = (А Ú В) Ú С
4. Правила поглощения
А Ù (А Ú В) = А	А Ú (А Ù В) = А
5. Дистрибутивность
А Ù (В Ú С) = (А Ù В) Ú (А Ù С)	А Ú (В Ù С) = (А Ú В) Ù (А Ú С)
6. Правила де Моргана
7. Свойства констант
А Ù 1 = А А Ù 0 = 0	А Ú 0 = А А Ú 1 = 1
8. Закон исключения третьего и закон противоречия
9. Снятие двойного отрицания
10. Формулы расщепления (склеивания)
11. Связь дизъюнкции, конъюнкции, отрицания и импликации
12. Выражение эквивалентности

Любая из этих равносильностей легко может быть доказана с помощью таблицы истинности.

Пример 23.

Рассмотрим одно из правил поглощения А Ù (А Ú В) = А.

Таблица 12

По таблице 12 видно, что результирующий столбец и столбец А совпадают на все наборах. Значит, формулы действительно равносильны.

Однако часто равносильность экономнее доказывать без составления полной таблицы истинности, а с помощью приведенных выше равносильностей.

Пример 24.

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

2. Упростить формулу: .

3. Определить, является ли формула тавтологией, противоречием или ни тем, ни другим:

a) ;

b) ;

c) ;

d) ;

e) .

Решение.

1. .

2.

3. a)

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

b) .

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

c)

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

d)

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

e)

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