Основные понятия, методы и алгоритмы

УДК 671.8

ББК 37

 

Шилихина К.М., Половинкин И.П., Половинкина М.В. Математическая логика. Методические указания к выполнению домашнего задания. Воронеж. ВГУ, 2020. –  24 с.

 

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

 

 

ÓШилихина К.М.,

Ó Половинкин И.П., Половинкина М.В.

Ó ВГУ

 

Цели и задачи домашнего задания

Целью выполнения задания является закрепление теоретического материала и развитие навыков его практического использования

 

Домашнее задание №1

Алгебра высказываний. Специальные виды формул

 

Дизъюнктивная нормальная форма, конъюктивная нормальная форма, полином Жегалкина

 

Основные понятия, методы и алгоритмы

Логические операции: отрицание ( или ), дизъюнкция (), конъюнкция (), импликация (), эквиваленция (), сложение по модулю 2 (  ), штрих Шеффера (  ), стрелка Пирса (), - однозначно определяются при помощи таблицы

Введем обозначение: , откуда следует .

 Определение 1.  Пусть  - булевы переменные. Формулы алгебры высказываний вида

                                                                   (1)

 

                                                                   (2)

 

                                                                         (3)

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

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

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

Определение 4.  Полиномом Жегалкина (ПЖ) называется сумма по модулю 2 различных монотонных конъюнкций.

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

                (4)

 

В дальнейшем для сокращения записи формул знак конъюнкции () в (1), (2), (4) будем опускать.

Дизъюнктивная нормальная форма (4) называется совершенной (СДНФ).

 

Теорема 2.  Для каждой булевой функции, отличной от тождественной единицы, существует и единственно (с точностью до порядка сомножителей) следующее представление в виде конъюнктивной нормальной формы

        (5)

 

Конъюнктивная нормальная форма (5) называется совершенной (СКНФ).

 

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

               (6)

где  - коэффициенты полинома Жегалкина.