Викиконспекты - Вклад участника [ru]

КНФ

2014-06-02T03:33:45Z

188.162.64.99: /* Алгоритм построения СКНФ по таблице истинности */ исправление опечатки

== КНФ ==
{{Определение
|definition =
Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
}}
Простая дизъюнкция
* '''полная''', если в неё каждая переменная (или её отрицание) входит ровно 1 раз;
* '''монотонная''', если она не содержит отрицаний переменных.

{{Определение
|definition =
КНФ (Конъюнктивная Нормальная Форма) — нормальная форма, в которой [[Определение булевой функции|булева функция]] имеет вид конъюнкции нескольких простых дизъюнктов.
}}
Пример КНФ:
<tex>f(x,y) = (x \lor y) \land (y \lor \neg{z})</tex>

== СКНФ ==
{{Определение
|definition =
СКНФ (Совершенная Конъюнктивная Нормальная Форма)''' — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых простых дизъюнкций
* каждая простая дизъюнкция полная
}}
Пример СКНФ:
<tex>f(x,y,z) = (x \lor \neg{y} \lor z) \land (x\lor y \lor \neg{z})</tex>

{{Теорема
|statement=
Для любой булевой функции <tex>f(\vec{x})</tex>, не равной тождественной единице, существует СКНФ, ее задающая.
|proof =
Поскольку инверсия функции <tex>\neg{f}(\vec x)</tex> равна единице на тех наборах, на которых <tex>f(\vec x)</tex> равна нулю, то СДНФ для <tex>\neg{f}(\vec x)</tex> можно записать следующим образом:
<tex>\neg{f}(\vec x) = \bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \wedge x_{n}^{\sigma_{n}}) </tex>, где <tex> \sigma_{i} </tex> обозначает наличие или отсутствие отрицание при <tex> x_{i} </tex>

Найдём инверсию левой и правой части выражения:
<tex> f(\vec x) = \neg ({\bigvee\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... ,x^{\sigma_{n}}) = 0} (x_{1}^{\sigma_{1}} \wedge x_{2}^{\sigma_{2}} \wedge ... \wedge x_{n}^{\sigma_{n}})}) </tex>

Применяя дважды к полученному в правой части выражению правило де Моргана, получаем:
<tex> f(\vec x) = \bigwedge\limits_{f(x^{\sigma_{1}}, x^{\sigma_{2}}, ... ,x^{\sigma_{n}}) = 0} (\neg{x_{1}^{\sigma_{1}}} \vee \neg{x_{2}^{\sigma_{2}}} \vee ... \vee \neg{x_{n}^{\sigma_{n}}} ) </tex>

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

== Алгоритм построения СКНФ по таблице истинности ==
# В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 0.
# Для каждого отмеченного набора записываем дизъюнкцию всех переменных по следующему правилу: если значение некоторой переменной есть 0, то в дизъюнкцию включаем саму переменную, иначе ее отрицание.
# Все полученные дизъюнкции связываем операциями конъюнкции.

== Пример построения СКНФ для медианы==
1. В таблице истинности отмечаем те наборы переменных, на которых значение функции равно 0.

{| class="wikitable" style="width:10cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| x || y || z || <tex> \langle x,y,z \rangle </tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 0 || 0
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 1 || 0
|-align="center" bgcolor=#F0F0F0
! 0 || 1 || 0 || 0
|-align="center" bgcolor=#F0F0F0
| 0 || 1 || 1 || 1
|-align="center" bgcolor=#F0F0F0
! 1 || 0 || 0 || 0
|-align="center" bgcolor=#F0F0F0
| 1 || 0 || 1 || 1
|-align="center" bgcolor=#F0F0F0
| 1 || 1 || 0 || 1
|-align="center" bgcolor=#F0F0F0
| 1 || 1 || 1 || 1
|}

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

{| class="wikitable" style="width:16cm" border=1
|+
|-align="center" bgcolor=#EEEEFF
| x || y || z || <tex> \langle x,y,z \rangle </tex> ||
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 0 || 0 || <tex>( x \lor y \lor z)</tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 0 || 1 || 0 || <tex>( x \lor y \lor \neg{z})</tex>
|-align="center" bgcolor=#F0F0F0
! 0 || 1 || 0 || 0 || <tex>(x \lor \neg{y} \lor z)</tex>
|-align="center" bgcolor=#F0F0F0
| 0 || 1 || 1 || 1 ||
|-align="center" bgcolor=#F0F0F0
! 1 || 0 || 0 || 0 || <tex>(\neg{x} \lor y \lor z)</tex>
|-align="center" bgcolor=#F0F0F0
| 1 || 0 || 1 || 1 ||
|-align="center" bgcolor=#F0F0F0
| 1 || 1 || 0 || 1 ||
|-align="center" bgcolor=#F0F0F0
| 1 || 1 || 1 || 1 ||
|}

3. Все полученные дизъюнкции связываем операциями конъюнкции.

<tex> \langle x,y,z \rangle = ( x \lor y \lor z) \land (\neg{x} \lor y \lor z) \land (x \lor \neg{y} \lor z) \land ( x \lor y \lor \neg{z})</tex>

==Примеры СКНФ для некоторых функций==
Стрелка Пирса: <tex> x \downarrow y = (\neg{x} \lor {y}) \land ({x} \lor \neg {y}) \land (\neg {x} \lor \neg {y}) </tex>

Исключающее или: <tex> x \oplus y \oplus z = (\neg {x} \lor \neg {y} \lor z) \land (\neg {x} \lor y \lor \neg {z}) \land (x \lor \neg {y} \lor \neg {z}) \land (x \lor y \lor z)</tex>

== Ссылки ==
* [http://ru.wikipedia.org/wiki/%D0%A1%D0%9A%D0%9D%D0%A4 СКНФ — Википедия]
* [http://dvo.sut.ru/libr/himath/w163rabk/index.htm Е.Л Рабкин, Ю.Б. Фарфоровская — Дискретная математика]

[[Категория: Дискретная математика и алгоритмы]]

[[Категория: Булевы функции ]]

Контактная схема

2013-12-08T12:55:03Z

188.162.64.99: /* Построение контактных схем */

{{Определение
|definition =
'''Контактная схема''' представляет собой ориентированный ациклический [[Основные определения теории графов|граф]], на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами'').
}}

==Принцип работы==
[[Файл:contact.png||right||200px]]
[[Файл:contactnot.png||right||200px]]
Зафиксируем некоторые значения переменным. Тогда '''замкнутыми''' называются ребра, на которых записана 1, ребра, на которых записан 0, называются '''разомкнутыми'''. Зафиксируем две вершины <tex>u</tex> и <tex>v</tex>. Тогда контактная схема вычисляет некоторую функцию <tex>f</tex> между вершинами <tex>u</tex> и <tex>v</tex>, равную 1 на тех наборах переменных, на которых между <tex>u</tex> и <tex>v</tex> есть путь по замкнутым ребрам.

==Построение контактных схем==
Любую контактную схему можно представить в виде комбинации 3 логических элементов:

* '''Конъюнкция'''
Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, что
последовательное соединение полюсов соответствует операции конъюнкции.

* '''Дизъюнкция'''
Результат дизъюнкции равен 0 только в случае, когда оба операнда равны 0. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению полюсов.

* '''Отрицание'''
Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.

Контактная схема

2013-12-08T12:54:00Z

188.162.64.99: /* Построение контактных схем */

{{Определение
|definition =
'''Контактная схема''' представляет собой ориентированный ациклический [[Основные определения теории графов|граф]], на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами'').
}}

==Принцип работы==
[[Файл:contact.png||right||200px]]
[[Файл:contactnot.png||right||200px]]
Зафиксируем некоторые значения переменным. Тогда '''замкнутыми''' называются ребра, на которых записана 1, ребра, на которых записан 0, называются '''разомкнутыми'''. Зафиксируем две вершины <tex>u</tex> и <tex>v</tex>. Тогда контактная схема вычисляет некоторую функцию <tex>f</tex> между вершинами <tex>u</tex> и <tex>v</tex>, равную 1 на тех наборах переменных, на которых между <tex>u</tex> и <tex>v</tex> есть путь по замкнутым ребрам.

==Построение контактных схем==
Любую контактную схему можно представить в виде комбинации 3 логических элементов.

* '''Конъюнкция'''
Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, что
последовательное соединение полюсов соответствует операции конъюнкции.

* '''Дизъюнкция'''
Результат дизъюнкции равен 0 только в случае, когда оба операнда равны 0. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению полюсов.

* '''Отрицание'''
Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над контактом знак отрицания.

Контактная схема

2013-12-08T12:52:01Z

188.162.64.99: /* Примеры некоторых контактных схем */

{{Определение
|definition =
'''Контактная схема''' представляет собой ориентированный ациклический [[Основные определения теории графов|граф]], на каждом ребре которого написана переменная или ее отрицание (ребра в контактных схемах называют ''контактами'', а вершины - ''полюсами'').
}}

==Принцип работы==
[[Файл:contact.png||right||200px]]
[[Файл:contactnot.png||right||200px]]
Зафиксируем некоторые значения переменным. Тогда '''замкнутыми''' называются ребра, на которых записана 1, ребра, на которых записан 0, называются '''разомкнутыми'''. Зафиксируем две вершины <tex>u</tex> и <tex>v</tex>. Тогда контактная схема вычисляет некоторую функцию <tex>f</tex> между вершинами <tex>u</tex> и <tex>v</tex>, равную 1 на тех наборах переменных, на которых между <tex>u</tex> и <tex>v</tex> есть путь по замкнутым ребрам.

==Построение контактных схем==
Любую контактную схему можно представить в виде комбинации 3 логических элементов.

* '''Конъюнкция'''
Результат конъюнкции равен 1 тогда и только тогда, когда оба операнда равны 1. В применении к контактным схемам это означает, что
последовательное соединение элементов соответствует операции конъюнкции.

* '''Дизъюнкция'''
Результат дизъюнкции равен 0 только в случае, когда оба операнда равны 0. Несложно догадаться, что в контактных схемах эта операция соответствует параллельному соединению элементов.

* '''Отрицание'''
Отрицание - это унарная операция, поэтому, чтобы показать её на контактной схеме достаточно написать над ребром графа знак отрицания.