Мат. логика

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

Перечень вопросов, выносимых на экзамен

1.	Организация процесса решения задач на ЭВМ. ...........................................................................	3
2.	Высказывание. Логические операции над высказываниями. .......................................................	5
3.	Формулы алгебры логики. Равносильные формулы алгебры логики. .........................................	7
4.	Равносильные преобразования формул. Алгебра Буля...............................................................	9
5.	Аналитическое представление функций алгебры логики...........................................................	10
6.	Минимизация булевых функций методом Квайна.......................................................................	11
7.	Минимизация булевых функций методом карт Карно и диаграмм Вейча. ................................	14
8.	Общезначимые формулы алгебры логики и их важнейшие свойства. ......................................	17
9.	Отношение логического следования и его связь с общезначимостью. .....................................	18
10.	Анализ рассуждений средствами алгебры высказываний. ........................................................	19
11.	Анализ рассуждений с помощью диаграмм Вейча......................................................................	20
12.	Понятие формулы исчисления высказываний. Система аксиом исчисления высказываний. .	22
13.	Правила вывода исчисления высказываний: правило подстановки, правило заключения......	23
14.	Формальное доказательство. .......................................................................................................	24
15.	Правила вывода исчисления высказываний: правило одновременной подстановки,
	правило сложного заключения. ....................................................................................................	25
16.	Правила вывода исчисления высказываний: правило силлогизма, правило контрпозиции. ...	26
17.	Правила вывода исчисления высказываний: правило снятия двойного отрицания. ................	27
18.	Формальный вывод. ......................................................................................................................	28
19.	Основные правила выводимости. ................................................................................................	29
20.	Теорема дедукции. ........................................................................................................................	30
21.	Теорема о корректности исчисления высказываний...................................................................	31
22.	Лемма о выводимости...................................................................................................................	32
23.	Теорема Поста (о полноте исчисления высказываний)..............................................................	36
24.	Проблемы аксиоматического исчисления высказываний: непротиворечивость, полнота,
	разрешимость, независимость. ....................................................................................................	38
25.	Понятие предиката. Логические операции над предикатами. ....................................................	39
26.	Понятие формулы логики предикатов. Значение формулы логики предикатов. ......................	41
27.	Равносильные формулы логики предикатов. ..............................................................................	42
28.	Предварённая нормальная форма. .............................................................................................	43
29.	Общезначимость и выполнимость формул логики предикатов. ................................................	44
30.	Проблема разрешимости для общезначимости и выполнимости применительно к логике
	предикатов. ....................................................................................................................................	45
31.	Метод аналитических таблиц. ......................................................................................................	47
32.	Силлогистика Аристотеля.............................................................................................................	50
33.	Аксиоматическое исчисление предикатов. Теоремы о корректности и полноте исчисления
	предикатов. ....................................................................................................................................	54
34.	Формализация арифметики натуральных чисел. ........................................................................	55
35.	Гёделевская нумерация................................................................................................................	57
36.	Теорема Гёделя о неполноте. ......................................................................................................	58
37.	Интуитивное определение алгоритма. Эквивалентность различных теорий алгоритмов.
	Тезис Чёрча. ..................................................................................................................................	59
38.	Машина Тьюринга. Вычисление функций на машинах Тьюринга. Тезис Тьюринга..................	60
39.	Частично-рекурсивные функции. Тезис Чёрча. ...........................................................................	64
40.	Нормальные алгоритмы Маркова. Тезис Маркова......................................................................	69
41.	Разрешимость и перечислимость множеств. Следствие теоремы Тарского. ...........................	71
42.	Нумерация машин Тьюринга. .......................................................................................................	73
43.	Существование невычислимых по Тьюрингу функций. ..............................................................	74
44.	Проблемы распознавания самоприменимости и применимости. ..............................................	75
45.	Теорема Райса. .............................................................................................................................	76

1. Организация процесса решения задач на ЭВМ.

Висторию компьютера удобно разбить на три этапа:

машинные ресурсы,

программирование,

формализация знаний.

Первый этап охватывает примерно 15 лет (1950 1965гг). Машин было мало, а нерешенных задач счетного характераболее, чем достаточно. Были созданы алгоритмические языки программирования типа Алгол, Фортран, Кобол и многие другие, что позволило резко ускорить процесс кодирования задач по ранее формализованным алгоритмам. Общие затраты на обработку данных в основном определялись величиной затраченного на них машинного времени. Центральной задачей этого этапа была экономия машинных ресурсов.

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

Технология решения задач на ЭВМ, сложившаяся на этом этапе и схематично показанная на рис. 1.1, получила статус традиционной.

На рис. 1.1 приняты следующие сокращения: КПконечный пользователь, А- программист-аналитик, ППприкладной программист, О- оператор, СПсистемный программист.

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

на этом этапе отвечали операционные

К П

Постановка задачи на языке конечного пользователя

А

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

П П

Программа

О

Стандартные средства			ЭВМ
математического						СП
обеспечения ЭВМ

результаты

Рис. 1.1

Второй этап также охватывает примерно 15 лет (1965 1980 гг.). К этому времени машинные ресурсы перестали быть основным фактором в оценке затрат на обработку данных. Расходы же на создание программ продолжали расти. Основная задача этого этапа заключалась в переходе от

эффективного исполнения

программ к

К П

К П

эффективному программированию.

Решению

этой

задачи

способствовало

А

А

появление режима разделения времени и

развитие интерактивных систем отладки с

терминалы

широким использованием дисплеев.

Однако, если при пультовой отладке

машина в основном простаивала, то в

пакетном режиме она в основном работала

Стандартные

Прикладные прог-

ЭВМ

впустую,

выполняя расчеты,

которые

средства математи-

раммы, математи-

База

ческого обеспечения

ческие модели пред-

данных

С П

программист,

«выдворенный»

по

ЭВМ

метных областей

технологическим

соображениям

к тому

времени из машинного зала, прекратил бы,

Рис. 1.2

увидев уже происшедшее. И ЭВМ вышли на

второе место в мире (после газет) по производству бумажной макулатуры.

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

Схема решения задач на ЭВМ на втором этапе изображена на рис. 1.2.

Третий этап берет свое начало в 1980 г. Окончание

количество

этапа

пока

неизвестно.

Для оценки ситуации,

1-динамика миро-

сложившейся к этому времени, полезно взглянуть на

вого парка ЭВМ

рис. 1.3.

Из рисунка видно,

что если до 1975 г. за каждой

2-динамика

ЭВМ

работал,

по

крайней

мере,

один

общей числен-

профессиональный программист, то уже к концу 1985

ности професси-

ональных про-

г. в большинстве случаев (по экспертным оценкам в 9

граммистов

случаях из 10

[99])

за пультом ЭВМ находился не

1975 г.

годы

программист,

а

так

называемый,

Рис.1.3

«непрограммирующий профессионал».

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

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

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

Как следует из рис. 1.2, успешное решение основной задачи данного этапа требует создания системными программистами таких средств, реализуемых внутри ЭВМ, чтобы все функции аналитика взяла на себя машина.

Какие же функции аналитика нужно суметь смоделировать в машине [187]:

прежде всего функции, связанные с общением конечного пользователя с аналитиком. Для связи КП и ЭВМ на языке пользователя ЭВМ должна располагать знаниями о языке, которые концентрируются в диалоговой системе. Обычно ее называют как диалоговый или лингвистический процессор (ДП);

подобно ДП ЭВМ должна аккумулировать в себе знания о предметной области, которые хранятся в специальной базебазе знаний (БЗ);

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

Структурная схема системы, построенной на основе названных блоков, изображена на рис. 1.4.

Монитор на рис. 1.4 осуществляет общее

КП

управление, синхронизируя работу всех блоков.

Вместе

эти

четыре

блока (ДП, БЗ,

П

и

ДИАЛОГОВЫЙ ПРОЦЕССОР

монитор)

образуют

некую

оболочку

П

Л

(«интеллектуальный уровень») обычной ЭВМ и

А

М

называются

ее

интеллектуальным

Н

О

интерфейсом.

И

Н

Р

И

ЭВМ

Решение любой задачи на ЭВМ предполагает

О

Т

В

О

выполнение

следующих

пяти

пунктов:

1-

Щ

Р

постановка задачи, 2- разработка алгоритма

И

К

решения задачи, 3- разработка программы на

БАЗА ЗНАНИЙ

каком-либо

алгоритмическом

языке,

4-

трансляция

программы,

5-

загрузка

Рис. 1.4

оттранслированной

программы

в

ЭВМ,

выполнение и получение результата.

На первом и втором этапах выполнение первых 3-х пунктов возлагалось на человека и только два последних пункта решались ЭВМ автоматически. Применение интеллектуального интерфейса на третьем этапе позволяет оставить за человеком только постановку задачи, а все остальное, необходимое для решения поставленной задачи, возложить на ЭВМ.

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

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

2. Высказывание. Логические операции над высказываниями.

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

Не всякое предложение является высказыванием. В частности, вопросительные и восклицательные предложения не относятся к высказываниям.

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

Логические операции над высказываниями

1.Отрицание или операция НЕ

Отрицанием высказывания х называется новое высказывание, которое определяется:

Читается «не x» или «неверно, что x».

Логический элемент, реализующий операцию НЕ, называется инвертором и на схемах обозначается так: (ГОСТ 2.743-82)

2.Конъюнкция (логическое умножение или операция «И»)

Конъюнкцией двух высказываний х, у называется новое высказывание, которое может быть обозначено

Логический элемент, реализующий операцию «И», называется конъюнктором, либо элементом типа «И». и на схемах обозначается так:

3.Дизъюнкция (логическое сложение или операция «ИЛИ»)

Дизъюнкцией двух высказываний х, у называется новое высказывание, которое определяется:

Логический элемент, реализующий эту операцию, называют дизъюнктором или элементом типа «ИЛИ».

4.Импликация (операция следования или операция «ЕСЛИ, ТО»)

Импликацией двух высказываний х, у называется новое высказывание, которое определяется:

Если х, то у. Из х следует у. х – условие (посылка).

у – следствие (заключение).

Логический элемент, реализующий эту операцию:

Замечание:

0	0	1
0	1	1
1	0	0
1	1	1

Употребление слов «если, то» в алгебре логики отлично от употребления их в обыденной речи.

В обыденной жизни если х – ложно, то высказывание если х, то у вообще не имеет

смысла.

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

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

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

5.Эквиваленция (операция равнозначности)

Эквиваленцией х, у называют новое высказывание, которое определяется:

читается как «х тогда и только тогда, когда у» или «Для того, чтобы х, необходимо и достаточно, чтобы у»

Логический элемент, реализующий операцию равнозначности, называется элемент равнозначности.

6.Операция Шеффера (операция «И-НЕ», операция штрих-Шеффера)

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

Читается как «х штрих-Шеффера у»

Логический элемент, реализующий операцию «И-НЕ», называется элементом Шеффера или элементом «И-НЕ» и обозначается так.

7. Операция Пирса (операция Вебба, операция стрелка Пирса, операция «ИЛИ-НЕ»)

Операция Пирса над двумя высказываниями х, у дает новое высказывание, которое определяется:

Логический элемент, реализующий операцию «ИЛИ-НЕ» называется элементом Пирса или элементом «ИЛИ-НЕ» и на схемах обозначается как:

8.Сложение по модулю два (операция неравнозначности)

Сложением по модулю два двух высказываний х, у называется новое высказывание, которое определяется:

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

Таблицы истинности рассмотренных логических операций сведем в единую таблицу такого вида:

x	y		x y	x y	x → y	x ↔ y	x / y	x ↓ y	x y
1	1	0	1	1	1	1	0	0	0
1	0	0	0	1	0	0	1	0	1
0	1	1	0	1	1	0	1	0	1
0	0	1	0	0	1	1	1	1	0

3.Формулы алгебры логики. Равносильные формулы алгебры логики.

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

Формулы алгебры логики будем обозначать большими латинскими буквами: А, В, С… Для упрощения записи формул введем следующие соглашения

1.Можно опускать скобки, придерживаясь следующего порядка действий ┐, , , ~, /,

2.Если над формулой стоит знак отрицания, то скобки можно опустить.

Равносильные формулы алгебры логики

Две формулы А и В называются равносильными, если их таблицы истинности совпадают. Запись А ≡ В означает, что А и В равносильны.

Приведем классификацию формул алгебры логики

		Хотя бы одно И;
Только И			Только Л
		Хотя бы одно Л
Общезначимые формулы		нейтральные	невыполнимые
выполнимые			невыполнимые
общезначимые		необщезначимые
Тождественно истинные;		Тождественно ложные;
тавтология		противоречия

Важнейшие равносильности алгебры логики можно разбить на три группы:

1.Основные равносильности.

1.	правило повторения
2.	(ff ≡ f - всегда)

3.

4.

5.

6.

7.- закон противоречия

8. - закон исключенного третьего

9.- правило двойного отрицания

чет		нечет
x	х	x		x
10.				- законы поглощения
11.
12.			- правило склеивания

2.Равносильности, выражающие одни логические операции через другие.

1.

2.

3.

законы Де Моргана

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

3.Равносильности выражающие основные законы алгебры логики.

Коммутативность:	Ассоциативность:
1.	7.
2.	8.
3.	9.
4.	10.
5.	11.
6.	12.	(?)
	13.

4. Равносильные преобразования формул. Алгебра Буля.

Равносильные преобразования формул

Равносильные преобразования используются:

1.для доказательства равносильностей,

2.для приведения формул к заданному виду,

3.для упрощения формул.

Примеры:

Доказать равносильность:

Цепочка равносильных преобразований имеет вид:

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

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

- общезначимая формула, или тождественно равная 1.

Алгебра Буля

Рассмотрим пустое множество М элементов любой природы М = {x, y, z,…}, в котором, определены отношения равенства и три операции +, *, -, подчиняющихся следующим аксиомам:

1.Коммутативный закон.

А) x + y = y + x Б) xy = yx

2.Ассоциативный закон.

А) x + (y + z) = (x + y) + z Б) x(yz) = (xy)z

3.Дистрибутивный закон.

А) (x + y)z = (xz) + (yz) Б) (xy) + z = (x + z)(y + z)

4.Закон повторения.

А) x + x = x Б) xx = x

5.Закон двойного отрицания.

6.Законы Де Моргана.

А) Б)

7.Закон поглощения. А)

Б) Такое множество М с указанными операциями называется булевой алгеброй.

Если под элементами x, y, z подразумевать высказывания, под операциями +, *, - подразумевать дизъюнкцию, конъюнкцию и отрицание, а знак = рассматривать как знак равносильности, то, как следует из перечисленных равносильностей, все аксиомы булевой алгебры выполняются.

Если для некоторой системы аксиом удается подобрать конкретные объекты и конкретные соотношения между ними так, что все аксиомы выполняются, то говорят, что найдена интерпретация (модель) данной системы аксиом. Это означает, что алгебра логики является интерпретацией (моделью) булевой алгебры. Алгебра Буля имеет и другие интерпретации. Например, если под элементами x, y, z рассматриваем множество, под операциями +, *, - соответственно понимаем операции объединение, пересечение и дополнение, а под знаком = понимаем знак равенства множеств, то мы приходим к алгебре множеств, в которой все аксиомы алгебры Буля выполняются.

5. Аналитическое представление функций алгебры логики.

Булева переменная
х1, х2,…,хn: x1 ϵ {0,1} – логические переменные (булевы переменные)
Булева функция
F(х1,…,хn): xi ϵ {0,1}, f ϵ {0,1} – переключательная функция	Таблица истинности:
2n наборов переменных		x1	x2	f
		0	0	0
- число различных БФ
		0	1	1
		1	0	1
Элементарное произведение		1	1	0

Логическое произведение r переменных, в котором каждая переменная входит 1 раз, называется элементарным конъюнктивным термом ранга r.

r=3

Элементарная сумма

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

r=3

Конституента единицы

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

n = 4			10 - тот набор, на котором он дает 1.
1	0	1	0
			Ставим отрицание на тем элементом, где 0.
1	1	0 0
			Конституента нуля

Элементарная сумма максимального ранга – конституента нуля. Конституента 0 это булева функция, которая принимает 0 значение только на 1 наборе. На остальных дает 1.

n = 4
1	0	1	0
1	0	0	1

ДНФ, СДНФ, КНФ, СКНФ

ДНФ – дизъюнкция элементарных произведений

fДНФ =

СДНФ (совершенная ДНФ)– все элементарные произведения имеют максимальный ранг СДНФ булевой функции это дизъюнкция всех конституент единицы, принимающих единичные

значения на тех же наборах, что и f.

fСДНФ =

КНФ – конъюнкция элементарных сумм

fКНФ = (х1 + х2 + х3)(х1 + х3 + + х5)

СКНФ (совершенная КНФ)– все элементарные суммы имеют максимальный ранг

СКНФ булевой функции f это конъюнкция всех конституент нуля, принимающих нулевые значения на тех же наборах, что и f.

fСКНФ =

Импликанта

φ – импликанта по отношению f, если она принимает значение 0 на всех наборах, где f тоже равно 0.

Простая импликанта

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

, если , , – не импликанты.

ДСНФ

ДСНФ – дизъюнкция всех простых импликант.