рефераты конспекты курсовые дипломные лекции шпоры

Раздел Информатика
/
Дизъюнктивные и конъюнктивные нормальные формы в алгебре высказываний

Реферат Курсовая Конспект

Выберите учебное заведение

Дизъюнктивные и конъюнктивные нормальные формы в алгебре высказываний

Дизъюнктивные и конъюнктивные нормальные формы в алгебре высказываний - раздел Информатика, ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ Если Х — Логическая Переменная, δ {0,1}, То Выражение ...

Если х — логическая переменная, δ {0,1}, то выражение

называется литерой. Литеры х и ¬х называются контрарными.

Элементарной конъюнкцией или конъюнктом называется конъюнкция литер. Элементарной дизъюнкцией или дизъюнктом называется дизъюнкция литер.

Пример 8. Формулы x∨¬y∨¬z и x∨y∨x∨¬x — дизъюнкты, формулы ¬x∧y∧z и x∧y∧¬x — конъюнкты, а ¬x является одновременно и дизъюнктом, и конъюнктом.

Дизъюнкция конъюнктов называется дизъюнктивной нормальной формой (ДНФ); конъюнкция дизъюнктов называется конъюнктивной нормальной формой (КНФ).

Пример 9. Формула (x∧¬y)∨(y∧z) — ДНФ, формула (х∨z∨¬y)∧(x∨z)∧y — КНФ, а формула x∧¬y является одновременно КНФ и ДНФ.

Теорема 2. Для любой формулы φ АВ существует ДНФ (КНФ) ψ АВ такая, что φ≡ψ.

Опишем алгоритм приведения формулы к ДНФ.

1. Выражаем импликацию, участвующую в построении формулы, через дизъюнкцию и отрицание, используя эквивалентность φ→ψ≡¬φ∨ψ.

2. Используя законы де Моргана, переносим все отрицания к переменным и сокращаем двойные отрицания пользуясь законом двойного отрицания.

3. Используя закон дистрибутивности φ∧(ψ∨χ)≡(φ∧ψ)∨(φ∧χ), преобразуем формулу так, чтобы все конъюнкции выполнялись раньше дизъюнкций.

В результате применения пп. 1-3 получается ДНФ, эквивалентная исходной формуле.

Пример 10. Привести к ДНФ формулу φ¬((x→y)∨¬(y→z)).

Решение. Выразим логическую операцию → через ∨ и ¬: φ≡¬((¬x∨y)∨¬(¬y∨z)). Воспользуемся законами де Моргана и двойного отрицания: φ≡¬(¬x∨y)∧¬¬(¬y∨z)≡(¬¬x∧¬y)∧(¬y∨z)≡(x∧¬y)∧(¬y∨z). Используя закон дистрибутивности, приводим формулу к ДНФ: φ≡(x∧¬y∧¬y)∨(x∧¬y∧z). Упростим полученную формулу: (x∧¬y∧¬y)∨(x∧¬y∧z)≡(1) (x∧¬y)∨(x∧¬y∧z)≡(2) x∧¬y (для преобразования (1) использовался закон идемпотентности, для (2) – закон поглощения). Таким образом, формула φ эквивалентными преобразованиями приводится к формуле x∧¬y, являющейся одновременно ДНФ и КНФ.

Приведение формулы к КНФ производится аналогично приведению ее к ДНФ, только вместо п. 3 применяется п. 3':

3'. Используя закон дистрибутивности φ∨(ψ∧χ)≡(φ∨ψ)∧(φ∨χ), преобразуем формулу так, чтобы все дизъюнкции выполнялись раньше, чем конъюнкции.

Пример 11. Привести к КНФ формулу φ(x→y)∧((¬y→z)→¬x).

Решение. Преобразуем формулу φ к формуле, не содержащей →: φ≡(¬x∨y)∧(¬(¬¬y∨z)∨¬x). В полученной формуле перенесем отрицание к переменным и сократим двойные отрицания: φ≡(¬x∨y)∧((¬¬¬y∧¬z)∨¬x)≡(¬x∨y)∧((¬y∧¬z)∨¬x). Используя закон дистрибутивности, приводим формулу к КНФ φ≡(¬x∨y)∧(¬x∨¬y)∧(¬x∨¬z). Упростим полученную формулу: (¬x∨y)∧(¬x∨¬y)∧(¬x∨¬z)≡(1)(¬x∨(y∧¬y))∧(¬x∨¬z)≡(2)¬x∧(¬x∨¬z)≡ ≡(3)¬x (для преобразования (1) использовался закон дистрибутивности, для (2) – эквивалентность 1 утверждения 1, для (3) — закон поглощения). Таким образом, формула φ эквивалентными преобразованиями приводится к формуле ¬x, являющейся одновременно ДНФ и КНФ.

2.1.5. Совершенные дизъюнктивные и конъюнктивные

нормальные формы

Пусть (х₁,..., х_n) — набор логических переменных, Δ=(δ₁,…,δ_n) — набор нулей и единиц. Конституентой единицы набора Δ называется конъюнкт К¹(δ₁,…,δ_n)=x₁^δ1∧x₂^δ2∧…∧x_n^δn. Конституентой нуля набора Δ называется дизъюнкт К⁰(δ₁,…,δ_n)=x₁^1-^δ1∨x₂^1-^δ2∨…∨x_n^1-^δn.

Отметим, что K¹(δ₁,δ₂,…,δ_n)=1 (K⁰(δ₁,δ₂,…,δ_n)=0) тогда и только тогда, когда x₁=δ₁, x₂=δ₂,…, x_n=δ_n.

Совершенной ДНФ называется дизъюнкция некоторых конституент единицы, среди которых нет одинаковых, совершенной КНФ называется конъюнкция некоторых конституент нуля, среди которых нет одинаковых. Таким образом, СДНФ (СКНФ) есть ДНФ (КНФ), в которой в каждый конъюнкт (дизъюнкт) каждая переменная х_i из набора {х₁,...,х_п} входит ровно один раз, причем входит либо сама х_i, либо ее отрицание ¬x_i.

Пример 12. Формула x₁∧¬x₂∧x₃ есть конституента единицы K¹(1,0,1), формула x∨y∨¬z есть конституента нуля K⁰(0,0,1), формула (x₁∧¬x₂)∨(¬x₁∧x₂) – СДНФ, формула (x∨y∨¬z)∧(¬x∨¬y∨z)∧(¬x∨y∨z) – СКНФ, а формула (x₁∧¬x₂∧x₃)∨(¬x₁∧x₂∧x₃)∨(x₁∧¬x₂∧x₃) не является СДНФ.

Теорема 3. Для любой не тождественно ложной (не тождественно истинной) формулы φ АВ существует единственая СДНФ (СКНФ) ψ АВ такая, что φ≡ψ.

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

Опишем алгоритм приведения формулы к СДНФ.

1. Приводим данную формулу к ДНФ.

2. Преобразовываем ее конъюнкты в конституенты единицы с помощью следующих действий:

а) если в конъюнкт входит некоторая переменная вместе со своим отрицанием, то мы удаляем этот конъюнкт из ДНФ;

б) если в конъюнкт одна и та же литера x^δ входит несколько раз, то удаляем все литеры х^δ, кроме одной;

в) если в конъюнкт x₁^δ1∧…∧x_k^δk не входит переменная у, то этот конъюнкт заменяем на эквивалентную формулу (x₁^δ1∧…∧x_k^δk∧y)∨(x₁^δ1∧…∧x_k^δk∧¬y);

г) если в полученной ДНФ имеется несколько одинаковых конституент единицы, то оставляем только одну из них.

В результате получается СДНФ.

Пример 13. Найти СДНФ для ДНФ φ(x∧¬x)∨x∨(y∧z∧y).

Решение. Имеем φ≡x∨(y∧z)≡(x∧y)∨(x∧¬y)∨(x∧y∧z)∨(¬x∧y∧z)≡

≡(x∧y∧z)∨(x∧y∧¬z)∨(x∧¬y∧z)∨(x∧¬y∧¬z)∨(x∧y∧z)∨(¬x∧y∧z)≡

≡(x∧y∧z)∨(x∧y∧¬z)∨(x∧¬y∧z)∨(x∧¬y∧¬z)∨(¬x∧y∧z).

Описание алгоритма приведения формулы к СКНФ аналогично вышеизложенному описанию алгоритма приведения формулы к СДНФ и оставляется читателю в качестве упражнения.

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ

Логика это наука о законах мышления Это одна из древнейших наук Основные законы логики были сформулированы еще древнегреческим мыслителем... Современная математическая логика определяется как раздел математики... Данное учебно практическое пособие соответствует учебной программе курса Математическая логика и теория алгоритмов...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Дизъюнктивные и конъюнктивные нормальные формы в алгебре высказываний

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

ПРОГРАММА КУРСА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕРИЯ АЛГОРИТМОВ
Тема 1. «Совершенные дизъюнктивные нормальные формы (СДНФ) и совершенные конъюнктивные нормальные формы (СКНФ) в алгебре высказываний (АВ)». Формулы АВ. Эквивалентность формул АВ.

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

Эквивалентные формулы алгебры высказываний
Как показано в примере 1, различные формулы могут иметь одинаковые таблицы истинности. Так возникает понятие эквивалентности формул. Формулы φ и ψ АВ называются

Определение формального исчисления
Введем общее понятие формального исчисления. Будем говорить, что формальное исчисление I определено, если выполняются четыре условия. 1. Имеется некоторое множество

Система аксиом и правил вывода
Используя понятие формального исчисления, определим исчисление высказываний (ИВ). Алфавит ИВ состоит из букв x,y,z,u,v, возможно с индексами (которые называются про

Теорема о дедукции в исчислении высказываний
Теорема 1(о дедукции). Пусть φ1,…,φm,φ,ψ – формулы ИВ. Тогда φ1,…,φm,φ⊢

Теорема о замене в исчисления высказываний
Формулы φ и ψ назовем эквивалентными (обозначим φ≡ψ), если φ⊢ψ и ψ⊢φ.

Свойства выводимых и эквивалентных формул исчисления высказываний
Утверждение 3.Пусть φ,ψ, χ – формулы ИВ. Тогда 1) ⊢φ→φ; 2) φ∧ψ⊢φ;

Высказываний
Теорема 3.Пусть φ, ψ, χ ‑ формулы ИВ. Тогда имеют место следующие эквивалентности: 1) φ∧ φ≡φ, φ∨

Высказываний
Формула φ(x1,…,xn) ИВ называется тождественно истинной (обозначается ⊨φ), если φ(x1,…,xn) – тож

Алгебраические системы
Часто объектом изучения в математике служит множество вместе с определенной на нем структурой. Например, поля, формирующие основу обычной арифметики, линейные пространства, обеспечивающие связь гео

Формулы логики предикатов
Большинство определений этого параграфа будут индуктивными. Введем понятие атомарной формулы сигнатуры Σ: 1) если t1, t2, T(Σ), то

В алгебраической системе
Дадим индуктивное определение истинности формулы φ(x1,…,xn) сигнатуры Σ на элементах a1,…,an А в алгебраической с

Логическое следствие в логике предикатов
Через обозначим кортеж переменных ; через ‑ . Пусть φ1(),…,φn(), ψ() – формулы сигнатуры . Формула ψ называетс

Эквивалентные формулы логики предикатов
Формулы φ и ψ сигнатуры называются эквивалентными (обозначается φ ≡ ψ), если φψ или ψ . Утвержден

Пренексная нормальная форма в логике предикатов
Формула φ сигнатуры Σ называется бескванторной, если она не содержит кванторов. Бескванторная формула φ является дизъюнктивной (конъюнктивной) нормальной форм

Система аксиом и правил вывода
Зафиксируем некоторую произвольную сигнатуру Σ и определим исчисление предикатов сигнатуры Σ (ИПΣ). Формулами ИПΣ

Предикатов
Утверждение 2.В ИПΣ выполнимы все эквивалентности ИВ из теоремы 3. Утверждение 3. Пусть φ

Исчисления предикатов
Теорема 4. Все доказуемые в ИПΣ формулы являются тождественно истинными. Доказательство проводим индукцией по длине вывода формулы. Очевид

Машины Тьюринга
Машина Тьюринга – это система, работающая в дискретные моменты времени и состоящая из следующих частей: конечная лента, разбитая на конечное число ячеек. В ка

Примитивно рекурсивные функции
Базисными функциями называются следующие функции: – нулевая функция; – функция следования; – функция выбора. Оператор суперпозиции (подстановки) ставит в соот

Частично рекурсивные функции
Оператор минимизации ставит в соответствие n+1-местной частичной функции n-местную частичную функцию так, что и или определены и не равны 0,

Совершенные дизъюнктивные нормальные формы, совершенные конъюнктивные нормальные формы
Построить таблицы истинности для следующих формул алгебры высказываний и привести эти формулы к СДНФ и СКНФ. 1. (x∧¬y)→(y∧z);

Логическое следствие в алгебре высказываний
Проверить истинность соотношений тремя способами (используя определение логического следствия и пп. 3,4 теоремы 2. 1. ; 2. ; 3. ; 4. ; 5. ; 6.

Исчисление высказываний
Пусть - формулы исчисления высказываний. Построить вывод формулы исчисления высказываний из данного множества гипотез. 1. ; 2. ; 3. ; 4. ;

Алгебраические системы.
Построить подсистему алгебраической системы , порожденную множеством (через обозначен булеан множества B, т.е. множество всех подмножеств множества B): 1. 2.

Формулы логики предикатов
Выписать все подформулы данной формулы сигнатуры и определить свободные и связанные переменные формулы: 1. 2. 3. 4. 5.

В алгебраической системе
Написать формулу Ф(х), истинную в алгебраической системе тогда и только тогда, когда 1. х=1; 2. х=2n для некоторого натурального

Логическое следствие в логике предикатов
Пусть – формулы логики предикатов, и . . Доказать следующие соотношения. 1. ; 2. ; 3. ; 4. ; 5. ; 6. ; 7. ;