УПП_Дискретная математика-1. Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики

• Название: Международный консорциум Электронный университет Московский государственный университет экономики, статистики и информатики
• Дата: 09.02.2023
• Размер: 6.65 Mb.
• Имя файла: УПП_Дискретная математика-1.doc
• Тип: Учебно-практическое пособие; #929287
• страница: 5 из 19

Математическая логика

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

2.1. Алгебра высказываний
Простейшую из формальных логических теорий называют алгеброй высказываний. Из высказываний состоит любое логическое рассуждение. Высказывание – предложение, относительно которого можно утверждать, истинно оно или ложно. Так, предложение «5>1», «13 делится на 5» – высказывания. Но «Который час?», «Да здравствует математика!» – не являются высказываниями в связи с данным определением. Если высказывание истинно (ложно) в любой логической ситуации, то оно называется тождественно истинным (ложным), или логической константой, обозначаемой соответственно И(Л). Высказывания, истинные в одних логических ситуациях и ложные в других, называются переменными высказываниями. Все приведенные выше высказывания представляют собой так называемые элементарные высказывания.
Логические операции
Обозначим элементарные высказывания латинскими буквами A, B, C, ... , X, Y, Z ...

Конъюнкция. Обозначается АВ (А&В, АВ), читается: А и В. Получили сложное высказывание, составленное из двух элементарных. Значение истинности или ложности высказывания, являющегося конъюнкцией двух элементарных высказываний А и В, задается следующей истинностной таблицей:

Таблица 2.1.1


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

Чаще пользуются более удобным обозначением: «И» – 1, «Л» – 0. В этих обозначениях истинностная таблица конъюнкции будет иметь вид
Таблица 2.1.2


Итак, конъюнкция двух элементарных высказываний истинна тогда и только тогда, когда оба элементарных высказывания истинны.
Дизъюнкция. Обозначается АВ, читается: А или В. При этом разделительный смысл союза «или» исключается. Истинностная таблица дизъюнкции имеет вид:
Таблица 2.1.3



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

Отрицание. Единственная логическая операция, относящаяся к одному высказыванию, – унарная, в отличие от остальных – бинарных. Обозначается: (>А, А), читается: не А. Истинностная таблица имеет вид:
Таблица 2.1.4


Импликация. Обозначается АВ (АВ), читается: если А, то В. При этом А называют посылкой, В – следствием. Импликация задается следующей истинностной таблицей:
Таблица 2.1.5


Импликация ложна тогда и только тогда, когда посылка А истинна, а следствие В – ложь.
Двойная импликация. Обозначается АВ (АВ), читается: А тогда и только тогда, когда В. Задается следующей истинностной таблицей:
Таблица 2.1.6



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

Приведем пример. Пусть А и В – элементарные высказывания: А – «Этот четырехугольник – параллелограмм», В – «Этот четырехугольник – ромб». Образуем из этих двух элементарных высказываний сложные, используя перечисленные логические связки.

Сложное высказывание АВ, очевидно, читается так: «Этот четырехугольник есть параллелограмм и ромб». Значения истинности и ложности этого высказывания определяется таблицей 2.1.2. Это высказывание считают истинным в том и только в том случае, когда оба высказывания А и В – истинны.

Дизъюнкция указанных высказываний АВ читается: «Этот четырехугольник есть параллелограмм или ромб». Значение истинности и ложности этого высказывания определяется таблицей 2.1.3. Очевидно, для импликации и двойной импликации получим соответственно АВ: «Если этот четырехугольник есть параллелограмм, то он – ромб»; АВ «Этот четырехугольник есть параллелограмм тогда и только тогда, когда он – ромб». Значение истинности или ложности этих высказываний определяется таблицами 2.1.5 и 2.1.6. Отрицание к А, т.е. , есть высказывание: «Неверно, что этот четырехугольник есть параллелограмм» или «Этот четырехугольник не параллелограмм».

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

Заметим, что число строк истинностной таблицы, очевидно, равно , где n – число элементарных высказываний.
Упражнение 2.1.1
Построим истинностную таблицу сложного высказывания:

Очевидно, истинностная таблица будет содержать строк. Скобки применяются, если нарушаются естественный порядок операций: отрицание, конъюнкция, дизъюнкция, импликация, двойная импликация. Скобки (АВ) указывают на то, что сначала нужно выполнить импликацию, затем найти (АВ)С. Скобки в выражении можно опустить. Заключительной операцией в построении истинностной таблицы для S будет дизъюнкция двух высказываний: (АВ)С и .

Таблица 2.1.7

А	В	С	АВ	(АВ)С
1	1	1	1	1	0	0	1	1
1	1	0	1	0	1	1	0	0
1	0	1	0	0	0	0	1	1
1	0	0	0	0	1	1	0	0
0	1	1	1	1	0	1	0	1
0	1	0	1	0	1	0	1	1
0	0	1	1	1	0	1	0	1
0	0	0	1	0	1	0	1	1

Итак, формула S задает высказывание, которое истинно на следующих наборах значений элементарных высказываний:

А=1	В=1	С=1	(все три элементарных высказывания истинны)
А=1	В=0	С=1	(А, С – истинны, В – ложно)
А=0	В=1	С=1	(А – ложно, В и С – истинны)
А=0	В=1	С=0	(В – истинно, А и С – ложны)
А=0	В=0	С=1	(С – истинно, А и В – ложно)
А=0	В=0	С=0	(все три высказывания ложны).

Формулы алгебры высказываний
Будем пользоваться следующими символами A, B, C, ... , X, Y, Z ...

• 
  переменные высказывания, 0, 1, И, Л – const, , , , ,
  
• 
  символы соответствующих логических операций.
  

Дадим определение формулы алгебры высказываний:

1. 
   отдельно стоящая буква A, B, C, ... , X, Y, Z ... – формула.
   
2. 
   если А, В – формулы, то формулами являются и ( ), ( ), (АВ), (АВ), (АВ), (АВ).
   
3. 
   Других формул нет.
   

Очевидно, сложное высказывание выше приведенного примера задано формулой S.

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

S₁: Х неверно сделал расчет или если Y считал задачу правильно, то и Z сделал это без ошибок.

S₂: Если Х правильно просчитал задачу, то либо Y ошибся, либо Z сделал ее верно.

S₃: Либо Х неверно просчитал задачу, либо Y решил ее верно в том и только в том случае, если Z решил ее верно.
Очевидно, данные сложные высказывания составлены из следующих элементарных.

А: Х правильно просчитал задачу

B: Y правильно просчитал задачу

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



Составим истинностные таблицы данных высказываний:
Таблица 2.18

А	В	С	ВС	S1		S2	ВС	S3
1	1	1	1	1	1	1	1	1
1	1	0	0	0	0	0	0	0
1	0	1	1	1	1	1	0	0
1	0	0	1	1	1	1	1	1
0	1	1	1	1	1	1	1	1
0	1	0	0	1	0	1	0	1
0	0	1	1	1	1	1	0	1
0	0	0	1	1	1	1	1	1

Из таблицы 2.1.8 видно, что высказывания S₁ и S₂ равносильны: S₁=S₂.
Приведем список основных равносильных формул алгебры высказываний:

	АА=А	идемпотентность
	АА=А
	АВ=ВА	коммутативность
	АВ=ВА
	(АВ)С=А(ВС)	ассоциативность
	(АВ) С=А (ВС)
	А (ВС)=(АВ) (АС)	дистрибутивность
	А (ВС)=(АВ) (АС)
	AИ=И
	AЛ=Л
	AИ=A
	AЛ=A
	A =И	закон исключенного третьего
	A =Л
		законы де Моргана
	=И
	=Л

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

,

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

Высказыванию, истинному во всех логически возможных случаях, т.е. логической константе, обозначаемой 1 или И, будет соответствовать универсальное множество. Высказыванию, ложному во всех логически возможных случаях, т.е. логической константе, обозначаемой 0 или Л, будет соответствовать пустое множество. Тогда дизъюнкции двух высказываний будет соответствовать объединение (сумма) их множеств истинности, конъюнкции – пересечение их множеств истинности, а отрицанию к высказыванию – дополнение к множеству истинности данного высказывания. Учитывая это и сравнивая список основных равносильных формул алгебры высказываний со списком свойств основных операций над множествами, убеждаемся в том, что операции алгебры высказываний образуют Булеву алгебру.

Заметим следующее: для того, чтобы убедиться в равносильности двух формул, можно построить их истинностные таблицы и убедиться в их совпадении. Равносильность формул можно установить также, убедившись в совпадении множеств истинности рассматриваемых высказываний. Так, в справедливости закона дистрибутивности №7 можно убедиться, изобразив на диаграммах Эйлера-Венна множества истинности левой и правой частей равенства (рис. 2.1.1).




.

Рис. 2.1.1
Установить равносильность формул можно также путем их преобразования. Так, заменяя импликацию равносильной ей формулой, получим равносильность формул S₁ и S₂ упражнения 2.1.2:
.
Рассмотрим некоторые упражнения на данную тему.
Упражнение 2.1.3
Указать множество наборов, удовлетворяющих уравнению
S=(xyyz)  x  y  z=0.

Решение получим, построив истинностную таблицу данной формулы. Убеждаемся в том, что на всех 8^ми наборах истинности и ложности данных высказываний x, y, z формула принимает значение 1, т.е. наборов , где бы S принимала значение 0 нет, формула S1, т.е. тождественно истинна, т.е. наборов где бы S=0 нет.

К тому же результату можно прийти, преобразовав S и используя список основных равносильных формул:

,

т.к. а) ,

б) .
Упражнение 2.1.4
Проверить равносильность двух формул и .

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

, .

Очевидно, =.
Упражнение 2.1.5
При составлении расписания на понедельник преподаватели просили, чтобы уроки проходили в следующем порядке:

1. 
   математика первым или третьим уроком;
   
2. 
   история – первым или вторым;
   
3. 
   литература – вторым или третьим.
   

Можно ли удовлетворить просьбы всех трех преподавателей и, если это возможно, то каким образом ?

Введем следующие элементарные высказывания:

А – математика – I^ый урок

В – математика – III^ий урок

С – история – II^ой урок

D – история – I^ый урок

E – литература – II^ой урок

F – литература – III^ий урок

Просьбы всех преподавателей выражены высказываниями S₁=АВ, S₂=CD, S₃=ED.

Высказывание, удовлетворяющее просьбы всех трех преподавателей, очевидно, есть конъюнкция S₁, S₂, S₃, т.е. S = S₁  S₂  S_3, и оно должно быть истинным, т.е. S=1. Применим дистрибутивный закон №7 в преобразованиях S:

S=(AB)(CD)(EF)=(ACBCADBD)(EF).
В данном случае конъюнкция AD=0, т.к. первым уроком математика и история одновременно быть не могут.
S=ACЕBCЕBDЕACFBCFBDF.
Очевидно, АСЕ=0, т.к. СЕ=0: второй урок не может быть одновременно уроком истории и литературы. Аналогично: ВСЕ=0, BCF=0, BDF=0, т.е. S= BDЕACF=1.

Дизъюнкция истинна, если одно из слагаемых истинно: BDЕ=1; ACF=1.

Конъюнкция высказываний истинна, если истинны все входящие в нее сомножители. В результате получаем два возможных варианта ответа:

1. 
   BDЕ=1, т.е. история – I^ый урок,
   

литература – II^ой урок,

математика – III^ий урок.

2. 
   ACF=1, т.е. математика – I^ый урок
   

история – II^ой урок,

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

«А достаточное условие для В», очевидно выражается формулой: АВ, а «А необходимое условие для В» – формулой ВА, которую называют конверсией импликации. В конверсии импликации посылка А и заключение В меняются местами.

Достаточное условие может быть выражено формулой, равносильной формуле АВ, а именно , называемой контроппозицией, а необходимое условие – формулой , называемой конверсией контроппозиции.
В рассуждениях эти равносильные формулы заменяют друг друга. Кроме того, «А достаточно для В» может быть выражено в виде «А только, если В», (не путать с «А если и только если В»), т.к. это означает: «Если не В, то не А», т.е.
=АВ.
Итак, получим:

«А достаточно для В»: АВ= , «А только, если В»;

«А необходимо для В»: .
Очевидно, необходимое и достаточное условие выражается двойной импликацией
Упражнение 2.1.6
Написать формулы следующих высказываний.

S₁: дифференцируемая функция непрерывна;

S₂: функция дифференцируема только в случае ее непрерывности;

S₃: функция непрерывна только в случае ее дифференцируемости;

S₄: дифференцируемость функции есть необходимое условие ее непрерывности;

S₅: дифференцируемость функции есть достаточное условие ее непрерывности;

S₆: дифференцируемость функции есть необходимое и достаточное условие ее непрерывности.

Введем в качестве элементарных имен высказывания: А – данная функция дифференцируема, В – данная функция непрерывна.

Очевидно: S₁=АВ; S₂: «А только, если В», т.е. «Если , то «, т.е. =АВ; S₃: «В только, если А», т.е. ; S₄=ВА; S₅=АВ; S₆=АВ.

Итак, высказывания S₁, S₂, S₅ выражают достаточность А для В, а высказывания S₃, S₄ – необходимость.
Функции алгебры высказываний
Основным понятием математической логики является понятие логической функции. Пусть областью определения аргумента является множество, состоящее из двух элементов, условно обозначаемых 1, 0. Если множество значений функции также состоит из двух элементов 1, 0, то такая функция называется логической функцией. В частности, элементом логической функции могут быть переменные высказывания, тогда сама функция также представляет собой некоторое высказывание, значение которого зависит от аргументов.

Пусть логическая функция зависит от n аргументов. Различных наборов значений истинности и ложности аргументов существует (строки истинностной таблицы). Зададимся вопросом, сколько существует различных логических функций, зависящих от n аргументов, т.е. сколько существует различных столбцов в истинностной таблице, содержащей строк. Так как каждой из строк может быть поставлено в соответствие одно из двух значений 1 или 0, то всего столбцов существует . Итак, число логических функций, зависящих от n аргументов N= , – конечное число. Различных формул алгебры высказываний, включающих в себя n переменных, существует бесчисленное множество. Оно разбивается на конечное число классов равносильных между собой формул.

Сформулируем определение логической функции. Пусть М – множество функций f(x₁, ... x_n), переменные которых x_i определены на множестве Е₂ (1,0), для которых f(₁, ... _n)Е₂, если _iЕ₂. Функции из множества М есть функции алгебры логики, или Булевы функции.

Среди переменных логической функции есть существенные переменные и фиктивные. Функция f(x₁, ... x_i-1, x_i, x_i+1, ... x_n) существенно зависит от переменной x_i, если найдутся два набора =(₁, ... _i-1, 0, _i+1, ... _n) и =(₁, ... _i-1, 1, _i+1, ... _n) такие, что f()f( ). В этом случае переменная x_i является существенной переменной и фиктивной в противном случае.

Если переменная x_{i –} фиктивная, то функцию f(x₁, ... x_i-1, x_i, x_i+1, ... x_n) можно свести к равной ей функции g(x₁, ... x_i-1, x_i+1, ... x_n) от (n-1)^ой переменной. Для этого нужно в таблице функции f вычеркнуть все строки, где x_i=1 (или x_i=0), и столбец, соответствующий переменной x_i.
Упражнение 2.1.7
Таблица 2.1.9

x1	x2	f
1	1	0
1	0	0
0	1	1
0	0	1

Функция f(x₁ x₂) задана таблицей 2.1.9. Содержит ли f(x₁ x₂) фиктивные переменные? Если да, требуется свести функцию «f» к равной ей функции «g» от одной переменной.

Проверим переменную x₁. Для этого сравниваем наборы переменных x₁, x₂, где x₁ принимает различные значения, а значения x₂ не меняются. Первая пара наборов – первая и третья строки данной таблицы, т.е. ₁=(1,1) ₁=(0,1) приводят к результату f(1,1)=0, f(0,1)=1, т.е. нашли пару наборов, где при перемене значений исследуемой переменной x₁ и сохранении остальных переменных (в данном случае одна переменная x₂) значение функции f меняется; f(₁)f( ₁), т.е. x₁ – существенная переменная.
При исследовании x₂ поступаем аналогично:

1. 
   ₁=(1,1) ₁=(1,0) f(₁)=f( ₁),
   
2. 
   ₂=(0,1) ₂=(0,0) f(₂)=f( ₂),
   

т.е. x₂ – фиктивная переменная.

x1	g
1	1
0	0

Вычеркиваем в табл. 2.1.9 первую и третью строки: (1,1) (0,1), где x₁=1 (или вторую и четвертую: (1,0) (0,0), где x₁=0) и столбец, соответствующий фиктивной переменной x₂, получим g(x₁)= f(x₁ x₂).
Упражнение 2.1.8
Построить логическую функцию по формуле
.
Какие из переменных являются существенными?

Построив истинностную таблицу формулы S, получим функцию, соответствующую данной формуле (табл. 2.1.10).

При различных значениях истинности и ложности переменной х₃ и фиксированных значениях переменных х₁ и х₂ значения функции одинаковы. Следовательно, х₃ – фиктивная переменная. Существенными являются переменные х₁ и х₂. Сравнивая вторую и четвертые строки табл. 2.1.10, обнаруживаем, что при одинаковых значениях истинности переменных х₁=1 х₃=0 и разных значениях х₂ (1,0), значения функции разные, т.е. f(1,1,0) ≠ f(1,0,0), следовательно, х₂ – существенная переменная. Сравнивая четвертую и восьмую строки таблицы, получим f(1,0,0) не равно f(0,0,0), т.е. х₁ – существенная переменная.
Таблица 2.1.10

х1	х2	х3					f
1	1	1	1	1	0	0	0
1	1	0	1	1	0	0	0
1	0	1	1	1	1	1	1
1	0	0	1	1	1	1	1
0	1	1	1	1	0	0	0
0	1	0	1	1	0	0	0
0	0	1	0	1	1	0	0
0	0	0	1	1	1	0	0

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


Таблица 2.1.11

x1	x2	g
1	1	0
1	0	1
0	1	0
0	0	0

Этой формуле соответствует функция g, получаемая из f удалением фиктивной переменной х₃ (табл. 2.1.11).

Выпишем все функции от двух переменных. Очевидно их будет =16 (табл. 2.1.12).
Таблица 2.1.12

х1	х2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
1	1	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
1	0	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
0	1	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
0	0	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Очевидно, введенные ранее связки , , ,  есть соответственно функции f₈, f₁₄, f₁₁, f₉. В качестве связок используются и другие функции, в частности

F₇ – штрих Шеффера х₁х₂,

F₁ – знак Лукашевича х₁х₂,

F₆ – разделительная дизъюнкция , соответствующая разделительному союзу «или».
Полные системы связок

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

Используя формулы, равносильные импликации и двойной импликации, получим, что дизъюнкция, конъюнкция, отрицание образуют полную систему связок. Используя закон де Моргана, приходим к тому, что (-), (-) – полные системы связок.

В самом деле из трех связок , , ^ можно исключить дизъюнкцию: или конъюнкцию: .

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

Набор таких связок, как отрицание и двойная импликация – неполон, так же как и {, }{, , , }.
Упражнение 2.1.9
Проиллюстрировать полноту связок (, ^) на примерах:



Очевидно, в данных формулах нужно заменить все связки, кроме (, ^).

а) Преобразуем S₁:



Применяя формулу поглощения, получим

, т.е. .

б) , где по закону де Моргана, так же как и

, т.е.
Формула S₂ стала более громоздкой, но представлена только двумя связками: , ^.