Шпаргалка по предмету "Дискретная математика"

   (х1…х2) наз-ся выполнимой  если сущ-ет набор высказываний  А1…Аn который обращает эту ф-лу в истинное (ложное) высказывание

   (х1…х2) наз-ся товтологией  ели она обрщается в истинное высказывание на всех наборах значений переменных.

   (х1…х2) наз-ся противоречием  если она обращается в ложное  высказывание на всех наборах  значений переменных.

Формулы алгебры логики   и    наз-ся эквивалентными если совпадают их таблицы истинности.

Есть два способа определения ~: таблица истинности и при n>4 метод эквивалентных преобразований.

 

15. Булевы функции: определение, способы задания. Элементарные булевы  функции.

Функцией алгебры логики (булевой ф-ей) наз-ся всякая ф-ия которая произвольному набору из 0 и 1 ставит в соответствии либо 0 либо 1. f: {0,1}  →{0,1}

Мн-во всех булевых ф-ий обозначается Р  поскольку всего имеется 2   наборов из 0 и 1 длинной n то

|P |=2

Задать булеву ф-ию можно различными способами:

1) таблицей истинности 

2) формулой

3) перечислением всех наборов  на которых ф-ия принимает значение 0 или же 1

Элементарными булевыми ф-ми от одного аргумента являются константы 0 и 1, тождественная ф-ия: х, отрицание: х

Элементарными булевыми ф-ми являются конъюнкция, дезъюнкция, импликация, эквивалентность, сложение по mod2, сумма Жигалкина, штрих Шеффера(антиконъюнкция), стрелка Пирса.

 

 

 

 

 

 

 

 

 

 

 

16. Нормальные формы формул  алгебры логики. Совершенные нормальные  формы. Приведение к СДНФ и  СКНФ.

Литерой наз-ся выражение вида

 

Из опр.                                                 Таким образом конъюнкция литеры

Конъюнкция                     в которой все переменные различные наз-ся элементарной коъюнкцией.

Дезъюнкция элементарных конъюнкций наз-ся дезъюнктивной нормальной формой.

Дезъюнкция в которой все переменные различны наз-ся элементарной.

Конъюнкция элементарных дезъюнкций наз-ся конъюнктивной нормальной формой.

Теорема: любая формула алгебры логики эквивалентна некоторой ДНФ.

Теорема: любая формула алгебры логики эквивалентна некоторой КНФ.

Привести формулу к ДНФ(КНФ) можно с помощь эквивалентных преобразований. Причем любая ф-ия алгебры логики может иметь бесконечно много представлений в виде ДНФ и КНФ, особое место среди эти представлении занимают совершенные формы СДНФ и СКНФ.

Теорема: любую булевю ф-ию тождественно не равную 0можно представить в виде

                                                                  Такое представление наз-ся СДНФ.

Алгоритм приведения к СДНФ

1) для   (х1…хn) сост. таблицу истинности

2) в ТИ выделяем те наборы (   …   ) на которых f(x1…xn) пр. 1

3) для каждого такого набора  образуем элементарную коъюнкцию

4) все полученные конъюнкции  соединяем знаком дезъюнкции

Теорема: любую булевую ф-ию отличную от тождественной единицы можно представить в виде формулы                                                                                такое представление наз-ся СКНФ

Алгоритм приведения к СКНФ:

1) сост. ТИ

2) в таблице истинности выделим  наборы такие что (   …   )=0

3) для каждого такого набора  сост элементарную дезъюнкцию

4) соединим знаком конъюнкции

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

17. Предикаты. Основные понятия.

Эти выражения не являются высказываниями. Однако при конкретных x,y,z  каждое из этих предложений становится высказыванием истинным или ложным. Такого рода предложения наз-ся предикатами.

Предикатом р(х1…хn) наз-ся ф-ия переменные которой х1…хn принимают значения из мн-ва М а сама ф-ия принимает значения 1 или 0. М- наз-ся предметной областью предиката. Х1…хn- предметными переменными. Предикат от n аргументов наз-ся n-местным предикатом.

Предикат Р(х1…хн) на мн-ве М наз-ся выполнимым если при некоторой подстановке х1…хн конкретных элем-ов из мн-ва М он обращается в истинное высказывание.

Р(х1…хн) заданный на мн-ве М наз-ся опровержимым если при некоторой подстановке вместо х1…хн конкретных элем-ов из мн-ва М, он обращается в ложное высказывание.

Мн-ом истинности предиката заданного на мн-ве М наз-ся совокупность всех наборов являющихся

                                                                      Таких что данный предикат обращается в истинное высказывание при подстановке х1=а1, х2=а2,….хн=ан

Р ={(a1…an) | ai € M≡1}

Предикат наз-ся тождественно истинным если при любой подстановке х1…хн он обращается в истинное высказывание.

Предикат Р(х1…хн) наз-ся тождественно ложным если при любой подстановке х1…хн он обращается в ложное высказывание.

Предикаты Р(х1…хн) и Q(х1…хн) заданные на одном и том же мн-ве наз-ся равносильными если равны их мн-ва истинности

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

18. Формулы логики предикатов.

Выражение построенное по следующим правила:

1) всякий нульместный предикатный  символ (переменная) это формула

2) всякий n-местный предикатный символ Р (х1…хн) где х1…хн свободные переменные это формула

3) F   и F   формулы, то F 

4) если F-формула в которой х-сводно то                             формулы. Причем если в F кроме х есть др переменные то они остаются свободными если были свободны в F; они остаются связанными если были связаны в F

5) других ф-ий в логике предикатов нет.

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

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

Формулу логики предикатов наз-ют тождественно истинной на мн-ве М (тождественно ложной на мн-ве М) если при всякой подстановке вместо предикатных переменных любых конкретных предикатов заданных на этом мн-ве она обращается в тожественно истинный (ложный) предикат.

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