2.1. Высказывания

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

2.3. Пропозициональные формулы

2.4. Булевы функции. Таблицы истинности

2.5. Булевы функции одной переменной

2.6. Булевы функции двух переменных

2.7. Существенные и несущественные переменные

2.8. Равносильные формулы. Основные равносильности

2.9. Основные тавтологии

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

2.11. Понятие двойственной функции

2.12. Некоторые двойственные функции

2.13. Элементарные канонические формы

2.14. Нормальные формы формул

2.15. Приведение формул к нормальным формам

2.16. Минимизация д.н.ф.

2.17. Полные системы функций. Полином Жегалкина

2.18. Функционально замкнутые классы функций

2.19. Понятие алгоритма. Описание машины Тьюринга

2.1. Высказывания

Определение. Высказывание – повествовательное утверждение, которое либо истинно либо ложно (не то и другое одновременно).

Примеры высказываний: "Тише едешь – дальше будешь", "Париж – столица Франции". Но "Как бы чего не вышло" или "Миру – мир" не являются высказываниями.

Определение. Высказывание называется простым (элементарным), если оно рассматривается как одно неделимое целое.

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

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

Определение. Конъюнкцией ("и") высказываний P и Q называется высказывание, истинное тогда и только тогда, когда оба истинны. Обозначается P&Q.

Таблица истинности:

Определение. Дизъюнкцией ("или") высказываний P и Q называется высказывание, ложное тогда и только тогда, когда оба ложны. Обозначается .

Таблица истинности:

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

Таблица истинности:

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

Таблица истинности:

Определение. Эквивалентностью высказываний P и Q называется высказывание истинное, когда истинностные значения P и Q совпадают, и ложное в противном случае. Обозначается или .

Таблица истинности:

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

Таблица истинности:

2.3. Пропозициональные формулы

Рассмотрим алфавит , где , ,.

Символы из называются переменными высказывания или пропозициональными переменными.

Символы из называются логическими связками.

Скобки из называются вспомогательными символами.

Определение. Пропозициональная формула определяется следующим образом:

1) пропозициональная переменная есть формула;

2) если P и Q – формулы, то Ø P, (P&Q), (PÚ Q) ,(P® Q) ,(PÅ Q) ,(P|Q), (P¯ Q) – формулы,

3) других формул нет.

При этом

а) внешние скобки у формул опускаются;

б) устанавливаются следующие приоритеты:

Ø – выполняется в первую очередь;

& – во вторую очередь;

Ú , ® , Å , |, ¯ – в третью очередь.

2.4. Булевы функции. Таблицы истинности

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

Способы задания:

1) таблицами истинности; при этом 0 интерпретируется как "ложь", а 1 – как "истина";
2) пропозициональными формулами.

Таблица истинностей некоторых логических связок:

2.5. Булевы функции одной переменной

2.6. Булевы функции двух переменных

2.7. Существенные и несущественные переменные

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

.

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

.

2.8. Равносильные формулы. Основные равносильности

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

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

2.9. Основные тавтологии

Определение. Формулы P и Q называются равносильными (обозначается ), если при любых значениях переменных значение формулы P совпадает со значением Q.

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

Замечание. Здесь P, Q и R —пропозициональные формулы.

2.11. Понятие двойственной функции

Определение. Функцией, двойственной к булевой функции , называется функция .

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

Теорема. (Принцип двойственности.) Пусть ,…, и — булевы функции и пусть = - сложная булева функция. Тогда

=

Следствие. Пусть P и Q —формулы. Если , тогда .

Принцип двойственности позволяет получать из доказанных равносильностей целый ряд новых. Кроме того, СКНФ(f)=.

2.12. Некоторые двойственные функции

2.13. Элементарные канонические формы

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

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

2.14. Нормальные формы формул

Определение. Дизъюнктивной нормальной формой (Д.Н.Ф.) называется произвольная дизъюнкция элементарных конъюнкций.

Определение. Конъюнктивной нормальной формой (К.Н.Ф.) называется произвольная конъюнкция элементарных дизъюнкций.

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

Определение. Д.Н.Ф. называется совершенной и обозначается С.Д.Н.Ф, если каждая переменная входит в каждую элементарную конъюнкцию ровно один раз с отрицанием или без.

Пример: – Д.Н.Ф; – С.Д.Н.Ф.

Теорема. Любая логическая функция кроме 0 имеет единственную С.Д.Н.Ф: .

Теорема. Любая логическая функция кроме 1 имеет единственную С.К.Н.Ф: .

Здесь .

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

Записать ее С.Д.Н.Ф. и С.К.Н.Ф.

С.Д.Н.Ф.(f)=

С.К.Н.Ф.(f)=

2.15. Приведение формул к нормальным формам

Любую логическую формулу (кроме 0) можно привести к С.Д.Н.Ф. следующим образом:

1. Все не булевские операции заменить на булевские (&, Ú , Ø ) c помощью равносильностей:

   ; ; ; ; .

2. Все отрицания "спустить" до переменных с помощью законов де Моргана.
3. Раскрыть скобки (дистрибутивность, ассоциативность).
4. Удалить лишние конъюнкции, повторения переменных в конъюнкциях и константы.

   Для приведения к С.Д.Н.Ф:

5. Расщепить те конъюнкции, которые содержат не все переменные.

2.16. Минимизация д.н.ф.

Д.Н.Ф, содержащую минимальное число вхождений переменных, будем считать минимальной.

Приведем 2 наиболее простых метода минимизации Д.Н.Ф. функции:

1. Группировка: элементарные конъюнкции , в ДНФ группируются в пары так, что после вынесения за скобку общего множителя K подформула имела вид или . Далее заменяем на эквивалентную ей конъюнкцию K.

   Пример:

   .

2. Метод Блейка состоит в применении двух правил:

а) обобщенное склеивание – первое правило. С помощью формулы производим операцию обобщенного склеивания в Д.Н.Ф. пока это возможно. Для этого в Д.Н.Ф. отыскиваем подформулы вида и добавляем к ним . На этом этапе формула усложняется.

б) поглощение – второе правило. Оно основано на равенстве

.

Находим в Д.Н.Ф. конъюнкции с минимальным числом сомножителей и все конъюнкции, их содержащие, вычеркиваем.

Пример: .

Разумно в Д.Н.Ф. сначала применить метод группировки (как более простой), а затем метод Блейка.

2.17. Полные системы функций. Полином Жегалкина

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

Примеры базисов:

— дизъюнктивный базис;

— конъюнктивный базис;

— базис Жегалкина;

— базис Пирса;

— базис Шеффера.

Определение Логическая функция, представленная над базисом называется многочленом Жегалкина. Он имеет вид:

,

где константы .

2.18. Функционально замкнутые классы функций

Ведем следующие классы Поста:

= – Класс функций, сохраняющих 0.

= – Класс функций, сохраняющих 1.

= – Класс самодвойственных функций.

= – Класс линейных функций.

= – Класс монотонных функций.

Каждый класс Поста является функционально замкнутым, т.е. все функции, реализованные формулами над данным классом, также принадлежат данному классу.

Таблица принадлежности функциональным классам основных булевых функций:

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

2.19. Понятие алгоритма. Описание машины Тьюринга

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

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

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

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

Дискретность. Решение задачи разбивается на этапы, каждый из которых прост и локален.

Детерминированность. После выполнения очередного этапа однозначно определено, что сделать на следующем этапе.

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

Массовость. Алгоритм служит для решения целого класса однотипных задач.

Конечность. Для решения задачи выполняется конечная последовательность шагов алгоритма.

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

Определение. Машиной Тьюринга (м-т) называется тройка , где —внешний алфавит, обычно ; —внутренний алфавит, элементами которого являются состояния управляющего устройства, —заключительное состояние, —начальное состояние; —программа, состоящая из команд вида: , где —один из символов: (налево), (направо), (на месте), , .

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

Шаг работы м-т. Если м-т имеет состояние , в обозреваемой ячейке записан символ , то выполняется команда , м-т переходит в состояние , в ячейке на место , записывается и головка сдвигается влево, вправо или остается на месте в зависимости от символа .

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

Конфигурацией (машинным словом) называется слово , где — слово на ленте левее головки, — слово правее головки, включая символ под головкой.

Говорят, что м-т применима к слову , если , начав работу на слове , машина остановится через конечное число шагов; если в результате получится слово , то пишут . Если не остановится, то она не применима к слову .