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

Предположим, что имеется некоторое множество элементарных высказываний (типа 2 х 2 = 4). Будем обозначать их начальными буквами латинского алфавита. Введем в рассмотрение высказывательные переменные – символы, вместо которых можно подставлять высказывания. Их будем обозначать последними буквами латинского алфавита (x, y, z, ...).

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

П р и м е р ы .

Определение:

1. Содержание

   • Дискретная математика.
   • Множества.
   • П римеры
   • Или по другому
   • Операции над множествами.
   • Основные свойства операций над множествами.
   • Алгебра высказываний.
   • Логические операции над высказываниями.
   • Отрицание.
   • Конъюнкция.
   • Эквиваленция
   • Импликация.
   • Формулы алгебры высказываний.
   • Элементарные высказывания, символы логических переменных – формулы;
   • Если f1 и f2 – формулы алгебры высказываний, то
   • Других формул алгебры высказываний нет.
   • Равносильность формул.
   • Совершенная дизъюнктивная нормальная форма.
   • Приведение формулы к сднф.
   • Совершенная конъюнктивная нормальная форма.
   • Приведение формулы к скнф.
   • Полнота и замкнутость.
   • Минимизация днф.
   • Способы задания булевых функций.
   • Табличный способ задания.
   • Графический способ задания.
   • Аналитический способ задания.
   • Элементы теории графов.
   • Матрицы графов.
   • Некоторые общие понятия теории графов.
   • Взвешенные графы и алгоритмы поиска кратчайшего пути.
   • Задача о кратчайших путях.
   • Элементы теории алгоритмов.
   • Понятие автомата.
   • Машина Тьюринга.
   • Автомат Мили.
   • Правило суммы.
   • Правило прямого произведения.
   • Размещения с повторениями.
   • Размещения без повторений.
   • Перестановки.
   • Сочетания.
   • Сочетания с повторениями.