Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Проблема разрешения. Нормальные формы формул алгебры высказываний. ⇐ ПредыдущаяСтр 4 из 4
Формулы алгебры высказываний подразделяются на типы: выполнимые, тождественно истинные, тождественно ложные. Определение. Формула алгебры высказываний называется тождественно истинной или тавтологией, если она принимает значение при всех значениях входящих в нее переменных высказываний. Для обозначения тавтологии используется знак ╞, который ставится перед формулой, являющейся тавтологией.
Примерами тавтологий являются формулы:
Определение. Формула алгебры высказываний называется выполнимой, если она принимает значение хотя бы на одном наборе значений входящих в нее переменных высказываний. Выполнимыми являются формулы:
Определение. Формула алгебры высказываний называется тождественно ложной или противоречием, если она принимает значение при всех значениях входящих в нее переменных высказываний. Тождественно ложными являются формулы: Можно поставить следующую задачу: указать единый способ (алгоритм), позволяющий для каждой формулы алгебры высказываний выяснить, является ли формула тождественно истинной, выполнимой, тождественно ложной. Поставленная задача, носит название проблемы разрешения. Очевидно, проблема разрешения алгебры высказываний разрешима. Для каждой формулы алгебры высказываний может быть составлена таблица истинности, которая дает ответ на поставленный вопрос. Пример. Выяснить, какой является формула . Составим для данной формулы таблицу истинности
Данная формула тождественно истинная. Однако практическое использование таблицы истинности для формулы при больших затруднительно. Существует другой способ, основанный на приведении формул к так называемой «нормальной форме». Определение. Элементарной конъюнкцией называется конъюнкция переменных высказываний или их отрицаний. Элементарными конъюнкциями являются формулы: . Определение. Элементарной дизъюнкцией называется дизъюнкция переменных высказываний или их отрицаний. Элементарными дизъюнкциями являются формулы: Теорема. (Критерий тождественной истинности элементарной дизъюнкции) Для того, чтобы элементарная дизъюнкция была тождественно истинна, необходимо и достаточно, чтобы в ней содержалась хотя бы одна пара слагаемых, из которых одно есть отрицание другого.
Например, элементарные дизъюнкции являются тождественно истинными, а элементарная дизъюнкция тождественно истинной не является. Теорема. (Критерий тождественной ложности элементарной конъюнкции) Для того, чтобы элементарная конъюнкция была тождественно ложна необходимо и достаточно, чтобы в ней содержалась хотя бы одна пара множителей, из которых один является отрицанием другого. Например, элементарные конъюнкции являются тождественно ложными, а элементарная конъюнкция тождественно ложной не является. Определение. Конъюнктивной нормальной формой (КНФ) формулы называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций. Примерами КНФ являются формулы Определение. Дизъюнктивной нормальной формой (ДНФ) формулы называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций. Примерами ДНФ являются формулы Для каждой формулы алгебры высказываний путем равносильных преобразований можно получить ее КНФ, причем не единственную, а также ее ДНФ, также не единственную.
|
||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-12-07; просмотров: 95; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 13.59.80.187 (0.008 с.) |