- •1.Множества. Операции над множествами
- •2.Бинарные отношения, их типы. Примеры
- •3.Перестановки с повторениями и без.
- •4.Сочетания с повторениями и без.
- •5.Высказывания. Операции над высказываниями.
- •6.Булевы функции. Теорема о числе булевых функций.
- •7.Формулы алгебры логики и их классификация, примеры
- •8.Законы равносильности.
- •9.Днф и кнф
- •10.Алгебра Жегалкина. Полином Жегалкина
- •11.Теоремы о разложении.
- •12.Сднф и скнф. Алгоритмы их нахождения.
- •13.Контактные и логические схемы.
- •14.Сокращенная днф и алгоритмы ее построения.
- •15.Минимальная днф. Метод импликации матриц.
- •16.Тупиковые днф
- •17.Полнота и замкнутость
- •18.Важнейшие замкнутые классы.
- •19.Алгоритм Поста.
- •20.Предикаты. Область истинности, теорема об области истинности
- •21.Операции над предикатами.
- •22.Формулы алгебры логики предикатов и их классификация
- •23.Законы Де Моргана
- •24.Закон пронесения квантора общности через конъюнкцию
- •25.Закон пронесения квантора существования через дизъюнкцию
- •26.Детерминированные функции от одной переменной
- •27.Детерминированные функции от двух переменных
- •28.Машина Тьюринга
- •29.Примитивно рекурсивные функции. Примеры
- •30. Рекурсивные функции. Примеры
5.Высказывания. Операции над высказываниями.
под высказыванием понимается такое предложение, которое либо истинно, либо ложно. Высказывание не может быть одновременно и истинным, и ложным.
Операции
Отрицанием высказывания называется новое высказывание, обозначаемое(читается: "не" или "не верно, что"), которое истинно, если высказываниеложно, и ложно, если высказываниеистинно.
Конъюнкцией двух.высказываний иназывается новое высказывание, обозначаемоеили(читается: "и"), которое истинно лишь в единственном случае, когда истинны оба исходных высказыванияи, и ложно во всех остальных случаях.
Дизъюнкцией двух высказываний иназывается новое высказывание, обозначаемое(читается "или"), которое истинно в тех случаях, когда хотя бы одно из высказыванийилиистинно, и ложно в единственном случае, когда оба высказыванияиложны.
Импликацией двух высказываний иназывается новое высказывание, обозначаемое(читается: "если, то", или "изследует", или "влечет", или "достаточно для", или "необходимо для"), которое ложно в единственном случае, когда высказываниеистинно, а— ложно, а во всех остальных случаях — истинно.
Эквивалентностью двух высказываний иназывается новое высказывание, обозначаемое(читается: "эквивалентно", или "необходимо и достаточно для", или "тогда и только тогда, когда", или ", если и только если"), которое истинно в том и только в том случае, когда одновременно оба высказыванияилибо истинны, либо ложны, а во всех остальных случаях — ложно.
6.Булевы функции. Теорема о числе булевых функций.
Функцией алгебры логики от переменныхназывается функция, принимающая значения 1, 0 и аргументы которой также принимают значения 1, 0. Обычно функции алгебры логики называют булевыми функциями.
Теорема 1. Число Булевых функций от переменных=;
В алгебре логики особое значение имеют следующие булевы функции, которые называют элементарными булевыми функциями:
– константа 0; – константа 1;– тождественная функция;
– отрицание х; – конъюнкция x и y;– дизъюнкция х и у;
– импликация х и у; – эквивалентность х и у;
– сложение х и у по mod2; – функция Шеффера;
– стрелка Пирса.
7.Формулы алгебры логики и их классификация, примеры
1) каждая «элементарная» булева функция – формула;
2) если некоторое выражение N есть формула, то тоже формула;
3) если некоторые выражения M и N есть формулы, то выражения ,,,тоже формулы;
4) других формул, кроме построенных по п.п.1), 2), 3), нет.
Формулы алгебры логики мы будет обозначать большими N, M, … Например, следующие выражения являются формулами алгебры логики:
,.
Две формулы N и M называются равносильными, если они определяют одну и ту же булеву функцию (запись N = M будет означать, что формулы N и M равносильны).
Классификация:
1)тафтология(если знач. Ф-лы истено при ɏ наборах переменных);
2)противоречие(если знач. Ф-лы ложно при ɏ наборах переменных);
3)выполнимая(если сущ. хоть 1 набор при котором знач. выполнимо);
) алгебры логики. Эти равносильности выражают свойства логических операций.
8.Законы равносильности.
Приведем перечень важнейших равносильностей (законов) алгебры логики. Эти равносильности выражают свойства логических операций.
– закон тождества;
– закон противоречия;
– закон исключительного третьего;
– закон двойного отрицания;
, – законы идемпотентности;
, – законы коммутативности;
, – законы дистрибутивности;
, – законы ассоциативности;
, – законы де Моргана;
,
,
, – законы поглощения;
, – законы склеивания.