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

КНФ

2010-11-03T03:46:33Z

Podgornova:

{{Определение
|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> можно записать следующим образом:

}}
==Алгоритм построения СКНФ по таблице истинности==
*В таблице отмечаем наборы переменных, которые приводят логическое выражение в состояние нуля.
*В дизъюнкцию записываем переменную без инверсии, если она в наборе равна 0, и с инверсией, если она равна 1.
*Полученные дизъюнкции связываем операциями конъюнкции

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

Медиана трёх: <tex>f(x,y,z) = ( 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>

КНФ

2010-10-29T18:15:43Z

Podgornova:

{{Определение
|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>

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

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

Медиана трёх: <tex>f(x,y,z) = ( 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>

КНФ

2010-10-29T18:14:29Z

Podgornova:

{{Определение
|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>

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

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

Медиана трёх: <tex>f(x,y,z) = ( 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>

КНФ

2010-10-10T18:13:16Z

Podgornova:

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

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

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

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

Медиана трёх: <tex>( 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>

КНФ

2010-10-10T18:12:04Z

Podgornova:

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

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

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

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

Медиана трёх: <tex>( x \lor y \lor z) \land (\neg x \lor y \lor z) \and (x \lor \neg y \lor z) \and ( x \lor y \lor \neg z)</tex>

КНФ

2010-10-08T05:16:05Z

Podgornova:

''' КНФ (Конъюнктивная Нормальная Форма)''' в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции нескольких дизъюнктов.

Пример КНФ:
<math>(x \or y) \and (y \or \neg z)</math>

''' СКНФ (Совершенная Конъюнктивная Нормальная Форма)''' — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых элементарных дизъюнкций
* в каждой дизъюнкции нет одинаковых переменных
* каждая элементарная дизъюнкция содержит каждую из входящих в данную КНФ переменных.

Пример СКНФ:
<math>(x \or \neg y \or z) \and (x\or y \or \neg z)</math>

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

==Примеры СКНФ для некоторых функций==
Стрелка Пирса: <math>(\neg x \or y) \and (x \or \neg y) \and (\neg x \or \neg y)</math>

Медиана трёх: <math>( x \or y \or z) \and (\neg x \or y \or z) \and (x \or \neg y \or z) \and ( x \or y \or \neg z)</math>

КНФ

2010-10-08T05:14:44Z

Podgornova:

''' КНФ (Конъюнктивная нормальная форма)''' в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции нескольких дизъюнктов.

Пример КНФ:
<math>(x \or y) \and (y \or \neg z)</math>

''' СКНФ (Совершенная Конъюнктивная Нормальная Форма)''' — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых элементарных дизъюнкций
* в каждой дизъюнкции нет одинаковых переменных
* каждая элементарная дизъюнкция содержит каждую из входящих в данную КНФ переменных.

Пример СКНФ:
<math>(x \or \neg y \or z) \and (x\or y \or \neg z)</math>

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

==Примеры СКНФ для некоторых функций==
Стрелка Пирса: <math>(\neg x \or y) \and (x \or \neg y) \and (\neg x \or \neg y)</math>

Медиана трёх: <math>( x \or y \or z) \and (\neg x \or y \or z) \and (x \or \neg y \or z) \and ( x \or y \or \neg z)</math>

КНФ

2010-10-08T05:13:00Z

Podgornova: Новая страница: «''' КНФ (Конъюнктивная нормальная форма)''' в булевой логике — нормальная форма, в которой б…»

''' КНФ (Конъюнктивная нормальная форма)''' в булевой логике — нормальная форма, в которой булева формула имеет вид конъюнкции нескольких дизъюнктов.

Пример КНФ:
<math>(x \or y) \and (y \or \neg z)</math>

''' СКНФ (Совершенная Конъюнктивная Нормальная Форма)''' — это такая КНФ, которая удовлетворяет условиям:
* в ней нет одинаковых элементарных дизъюнкций
* в каждой дизъюнкции нет одинаковых переменных
* каждая элементарная дизъюнкция содержит каждую из входящих в данную КНФ переменных.

Пример СКНФ:
<math>(x \or \neg y \or z) \and (x\or y \or \neg z)</math>

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

==Примеры СКНФ для некоторых функций==
Стрелка пирса: <math>(\neg x \or y) \and (x \or \neg y) \and (\neg x \or \neg y)</math>

Медиана трёх: <math>( x \or y \or z) \and (\neg x \or y \or z) \and (x \or \neg y \or z) \and ( x \or y \or \neg z)</math>