Элементы математической логики

1) Высказывание логических операций

Высказывание - это предложение которое может определить истинно оно или нет
а=1 - истинное высказывание
а=0 - ложно высказывание

Инверсия (Отрицание) image

Конъюнкция(Умножение) image

Дизъюнкция(Сложение) image

Импликация(Следствие) image

Эквиваленция(тождественное равенство) image

Штрих Шеффера(Отрицание конъюнкции) image

Стрелка Пирса(Отрицание дизъюнкции) image

Сумма по модулю 2(Отрицание эквиваленции) image

2) Таблица истинности

Таблица истинности - это таблица описывающая логическую функцию image

Алгоритм составления

  1. Определяют кол-во строк= 2n+1(n-кол-во простых выражений)
  2. Определяют кол-во столбцов: кол-во переменных + кол-во логических операций
  3. Заполняют столбцы результатом выполнения

3) Виды формул

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

3.Формула называется тождественно - ложной если она принимает значение "ложно" при всех значениях переменных входящих в нее

4) Законы логики

  1. Де Моргана image
  1. Правила операций с константами image

3.Правила идемпотентности image

  1. Инверсия image

5.Снятие двойного отрицания image

Снятие импликации image

Снятие эквиваленции image

5) Нормальные формы

  1. Элементарная конъюкция - это конъюкция данных переменных
  1. Элементарная дизъюнкция - данных переменных или их отрицаний

6) Булевы функции

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

Формулы

Построения Сднф

  1. Выбрать в таблице строки которых значение функций = 1
    2.На соответствующих наборах переменных составить элементарные конъюкции взять саму переменную если ее значение 1 и инверсию переменной если значение 0
    3.соединить конъюкцию знаком дизъюнкции

Построение Скнф

  1. Выбрать строки с значением 0
    2.На соответствующих наборах переменных составить элементарные дизъюнкции взять саму переменную если ее значение 0 и инверсию переменной если значение 1
    3.Соединить дизъюнкцию знаком конъюнкции

7) Нахождение МДФ методом Квайна

  1. Записать в виде СДНФ
    2.Проводя все возможные склеивания привести формулу и сокращение ДНФ
  2. Построить импликантную матрицу

8) Многочлен Жегалкина это многочлен являющиеся суммой констант 0 или 1 и различных одночленов в которые каждая переменная входит не выше чем в 1 степени

9) Свойства операции сумма по модулю 2

  1. image
  2. image
  3. image
  4. image
  5. image
  6. image

10) Алгоритм составления многочлена Жегалкина

  1. Составить СДНФ для буливой функции
    2.Каждую инверсию переменной заменить по формуле
  2. Все знаки дизъюнкции заменить знаком по модулю 2
  3. Раскрыть скобки и привести к виду (*)

11) Классы Поста
1.Класс функций сохраняющих константу 0
f(0,0...0)=0
2.Класс функций сохраняющих константу 1
f(1,1...1)=1

  1. Класс самодвойственных функций (S):
    f(0,0)=f(1,1)
    f(0,1)=f(1,0)
    4.Класс монотонных функций(M)
  2. Линейные функции (L) функция называется линейной если ее можно представить в виде многочлена Жегалкина