Таблицы
истинности и их построение. СКНФ И СДНФ
Гладких
Д.В,
студ.
ГБПОУ НМК,
М.А.
Исхаков,
Преподаватель
Аннотация: Дискретная математика
имеет значительное значение в ряде научных и технических областей, таких как
информатика, криптография и алгоритмы. Логические выражения и их нормальные
формы занимают центральное место среди ключевых понятий данной дисциплины. Совершенная
конъюнктивная нормальная форма (СКНФ) и совершенная дизъюнктивная нормальная
форма (СДНФ) являются ключевыми способами представления логических функций. В
данной статье мы рассмотрим процесс создания таблиц истинности, а также
детально проанализируем СКНФ и СДНФ на конкретных примерах.
Ключевые слова: Дискретная математика, алгоритмы,
СКНФ, СДНФ.
Truth Tables and Their Construction. CNF and DNF
Gladkikh D.V,
Student
Iskhakov M.A,
Teacher
Abstract: Discrete mathematics plays a significant role in
various scientific and technical fields, including computer science,
cryptography, and algorithms. Logical expressions and their normal forms are
central to key concepts in this discipline. Perfect conjunctive normal form
(PCNF) and perfect disjunctive normal form (PDNF) are key ways to represent
logical functions. This paper examines the process of creating truth tables and
then provides a detailed analysis of CNF and DNF through concrete examples.
Keywords: Discrete mathematic, algorithms, CNF, DNF.
RU version
Таблицы истинности и
их построение
Основные логические
операции
1)
Конъюнкция (И, AND, ∧): A ∧ B истинно тогда, когда оба A и B истинны.
2)
Дизъюнкция (ИЛИ, OR, ∨): A ∨ B истинно тогда, когда хотя бы одно из A или B
истинно.
3)
Отрицание (НЕ, NOT, ¬): ¬A истинно тогда, когда A
ложно.
4)
Импликация (ЕСЛИ, TO, →): A → B истинно тогда, когда-либо
A ложно, либо B истинно.
5)
Эквиваленция (ТОЛЬКО ЕСЛИ, ↔): A ↔ B истинно тогда и только
тогда, когда A и B имеют одинаковые значения.
При построении таблицы
истинности для логического выражения важно учитывать порядок выполнения
логических операций.
Порядок выполнения
1.
Выражения
в скобках.
2.
Отрицание
(¬).
3.
Конъюнкция
(AND, ∧).
4.
Дизъюнкция
(OR, ∨).
5.
Импликация
(→).
6.
Эквиваленция
(↔).
Построение таблицы истинности
Таблица
истинности - это своего рода "инструкция" для логического правила.
Она показывает, что должно получиться на выходе, если мы подставим определенные
значения на вход. Это помогает нам убедиться, что правило работает именно так,
как задумано.
Пример 1 Решение таблицы истинности:
Рассмотрим
выражение: (А ∨
B) → (¬A)
|
A
|
B
|
¬A
|
А ∨
B
|
(А ∨
B) → (¬A)
|
|
0
|
0
|
1
|
0
|
0
|
|
0
|
1
|
1
|
1
|
0
|
|
1
|
0
|
0
|
1
|
1
|
|
1
|
1
|
0
|
1
|
1
|
Пояснение решения
Давайте
разберем логику шаг за шагом для первой строки, где A = 0 и B = 0:
1)
Значения
переменных:
·
A
присвоено значение 0.
·
B
присвоено значение 0.
2)
Нахождение
¬A (НЕ A):
·
Так как A
равно 0, отрицание A (¬A) равно 1.
3)
Нахождение
A ∨ B (A ИЛИ B):
·
A ∨ B равно 0 ∨ 0, что в итоге равно 0.
(Операция ИЛИ истинна, если хотя бы одно из значений истинно. Так как оба
значения ложны, результат ложен.)
4)
Нахождение
(A ∨ B) → (¬A) (ЕСЛИ A ИЛИ B, ТО НЕ A):
·
Выражение
становится (0) → (1).
·
Это
истинно, так как импликация ложна только тогда, когда предпосылка истинна, а
заключение ложно. Здесь предпосылка ложна (0), поэтому импликация истинна (1).
Совершенная Дизъюнктивная Нормальная Форма (СДНФ)
Представьте себе, что логическая функция - это как
рецепт, где каждая строка - это набор ингредиентов, а результат - это то, что
вы получаете в конце. СДНФ - это способ переписать этот рецепт, чтобы все
ингредиенты были перечислены в каждом пункте, но в разных вариантах - как есть
или в обратном виде.
Например, вместо "мука или сахар" в СДНФ будет
"мука ИЛИ не сахар" или "не мука ИЛИ сахар".
Таким образом, вы получаете не просто набор
ингредиентов, а полный список всех возможных комбинаций, что позволяет четко
понять, как работает логическая функция.
Этапы по построению СДНФ
1.
Создать
таблицу истинности для заданного логического выражения.
2.
Выделить
строки таблицы, в которых логическое выражение истинно.
3.
Для
каждой строки, где выражение истинно, составить элементарную конъюнкцию,
включающую все переменные этой строки.
4.
Объединить
все полученные элементарные конъюнкции с помощью операции дизъюнкции (ИЛИ).
Пример 2:
СДНФ
Рассмотрим
логическое выражение: A∧(B∨¬C).
Давайте
создадим таблицу, которая покажет нам, как работает построение СДНФ.
|
A
|
B
|
C
|
¬C
|
B∨¬C
|
A∧(B∨¬C)
|
|
0
|
0
|
0
|
1
|
1
|
0
|
|
0
|
0
|
1
|
0
|
0
|
0
|
|
0
|
1
|
0
|
1
|
1
|
0
|
|
0
|
1
|
1
|
0
|
1
|
0
|
|
1
|
0
|
0
|
1
|
1
|
1
|
|
1
|
0
|
1
|
0
|
0
|
0
|
|
1
|
1
|
0
|
1
|
1
|
1
|
|
1
|
1
|
1
|
0
|
1
|
1
|
СДНФ составляется по
строкам, где выражение истинно (1):
·
A=1,B=0,C=0
·
A = 1, B = 0, C = 0
·
A=1,B=0,C=0
·
A=1,B=1,C=0
·
A = 1, B = 1, C = 0
·
A=1,B=1,C=0
·
A=1,B=1,C=1
·
A = 1, B = 1, C = 1
·
A=1,B=1,C=1
Ответ: СДНФ: (A¬B¬C ∨ AB¬C ∨ ABC)
СДНФ позволяет
представлять логические функции в стандартизированной форме, что упрощает их
анализ и дальнейшую обработку
Совершенная Конъюнктивная Нормальная Форма (СКНФ)
Представьте, что логическая функция - это головоломка,
где нужно собрать все части, чтобы получить правильный ответ. СКНФ - это
способ переписать головоломку, разделив её на блоки, где каждая часть содержит
все "кубики" (переменные) в разных вариантах - как есть или
перевернутыми.
Например, вместо "красный или синий" в СКНФ
будет "красный И синий" или "не красный И не синий".
Таким образом, вместо единой сложной задачи вы получаете
набор более простых, что позволяет понять логическую функцию шаг за шагом.
Этапы по построению СКНФ
Давайте попробуем
разобраться с логическим выражением, используя таблицу!
1.
Создадим таблицу, где
запишем все варианты "входов" (значений переменных) и соответствующие
им "выходы" (результат работы логического выражения).
2.
Отметим строки, где
"выход" – "ложь".
3.
Для каждой такой строки
запишем "правило", включающее все переменные, но только те, которые в
этой строке имеют значение "истина".
4.
Соединим эти правила с
помощью "И", чтобы получить выражение, которое будет истинным только
тогда, когда все правила ложны.
Таким образом, мы
получим "рецепт" для нашего логического выражения, но
"перевернутый" – он будет показывать, когда наше выражение будет
ложным.
Пример
3:
Рассмотрим
логическое выражение: A∧(B∨¬C).
Давайте
создадим таблицу, которая покажет нам, как работает построение СКНФ.
|
A
|
B
|
C
|
¬C
|
B∨¬C
|
A∧(B∨¬C)
|
|
0
|
0
|
0
|
1
|
1
|
0
|
|
0
|
0
|
1
|
0
|
0
|
0
|
|
0
|
1
|
0
|
1
|
1
|
0
|
|
0
|
1
|
1
|
0
|
1
|
0
|
|
1
|
0
|
0
|
1
|
1
|
1
|
|
1
|
0
|
1
|
0
|
0
|
0
|
|
1
|
1
|
0
|
1
|
1
|
1
|
|
1
|
1
|
1
|
0
|
1
|
1
|
СКНФ составляется по
строкам, где выражение ложно (0):
Ответ: СКНФ: (A∨B∨C)
∧ (A∨B∨¬C) ∧ (A∨¬B∨C)
∧ (A∨¬B∨¬C) ∧ (¬A∨B∨¬C)
СКНФ является удобным
способом представления логических функций, поскольку позволяет их анализировать
и упрощать.
Преимущества и
применение СКНФ и СДНФ
- Стандартизация: Обе формы обеспечивают стандартизированное
представление логических функций, что упрощает их анализ и манипуляцию.
- Упрощение анализа: Приведение логических выражений к СКНФ
или СДНФ упрощает процессы верификации и тестирования логических схем.
- Универсальность: Эти нормальные формы находят применение в
различных областях, таких как проектирование логических схем, оптимизация
алгоритмов и задачи криптографии.
СКНФ и СДНФ являются
важными инструментами в дискретной математике, обеспечивая структурированный и
понятный способ представления сложных логических выражений.
EN version
Truth
Tables and Their Construction
Basic
Logical Operations
1)
Conjunction (AND,
∧): A ∧ B is true only when both A and B are
true.
2)
Disjunction (OR, ∨): A ∨ B is true when at least one of A or
B is true.
3)
Negation (NOT,
¬): ¬A is true when A is false.
4)
Implication (IF,
THEN, →): A → B is true whenever A is false or B is true.
5)
Equivalence (IF
AND ONLY IF, ↔️): A ↔️ B is true if and only if A and B have the same values.
When
constructing a truth table for a logical expression, it's crucial to consider
the order of operations.
Order of
Operations
1)
Expressions in parentheses.
2)
Negation (¬).
3)
Conjunction (AND, ∧).
4)
Disjunction (OR, ∨).
5)
Implication (→).
6)
Equivalence (↔️).
Truth Table Construction
A truth table is like an "instruction
manual" for a logical rule. It shows the output for each possible
combination of inputs. This helps ensure the rule operates as intended.
Example 1:
Solving a Truth Table
Consider the
expression: (A ∨ B) → (¬A)
|
A
|
B
|
¬A
|
А ∨
B
|
(А ∨
B) → (¬A)
|
|
0
|
0
|
1
|
0
|
0
|
|
0
|
1
|
1
|
1
|
0
|
|
1
|
0
|
0
|
1
|
1
|
|
1
|
1
|
0
|
1
|
1
|
Explanation of the solution
Let's go
through the logic step by step for the first line, where A = 0 and B = 0:
1)
Variable values:
·
A is assigned a value of 0.
·
B is assigned a value of 0.
2)
Finding ¬A (NOT A):
·
Since A is equal to 0, the
negation of A (¬A) is 1.
3)
Finding A ∨ B (A OR B):
·
A ∨
B is equal to 0 ∨ 0, which ultimately equals 0. (The OR operation is
true if at least one of the values is true. Since both values are false, the
result is false.)
4)
Finding (A ∨ B) → (¬A) (IF A OR B, THEN NOT A):
·
The expression becomes (0) → (1).
·
This is true because implication
is false only when the premise is true and the conclusion is false. Here, the
premise is false (0), so the implication is true (1).
Conjunctive Normal Form (CNF)
Imagine a
logical function like a recipe, where each line represents a set of ingredients,
and the outcome is what you get at the end. CNF is a way to rewrite this recipe
so that all ingredients are listed in every step, but in different variations –
as is or reversed.
For example,
instead of "flour or sugar" in CNF, it would be "flour AND not
sugar" or "not flour AND sugar".
This way, you
get not just a set of ingredients, but a complete list of all possible
combinations, allowing you to clearly understand how the logical function
works.
Stages of
CNF Construction
1) Create a truth table for the given
logical expression.
2) Highlight the rows in the table where
the logical expression is true.
3) For each row where the expression is
true, create an elementary conjunction, including all variables from that row.
4) Combine all resulting elementary
conjunctions using the disjunction (OR) operation.
Example 2:
CNF
Let's consider the logical expression: A∧(B∨¬C).
Let's create a table to demonstrate how CNF is
constructed.
|
A
|
B
|
C
|
¬C
|
B∨¬C
|
A∧(B∨¬C)
|
|
0
|
0
|
0
|
1
|
1
|
0
|
|
0
|
0
|
1
|
0
|
0
|
0
|
|
0
|
1
|
0
|
1
|
1
|
0
|
|
0
|
1
|
1
|
0
|
1
|
0
|
|
1
|
0
|
0
|
1
|
1
|
1
|
|
1
|
0
|
1
|
0
|
0
|
0
|
|
1
|
1
|
0
|
1
|
1
|
1
|
|
1
|
1
|
1
|
0
|
1
|
1
|
CNF is constructed
based on the rows where the expression is true (1)
·
A=1,B=0,C=0
·
A = 1, B = 0, C =
0
·
A=1,B=0,C=0
·
A=1,B=1,C=0
·
A = 1, B = 1, C =
0
·
A=1,B=1,C=0
·
A=1,B=1,C=1
·
A = 1, B = 1, C =
1
·
A=1,B=1,C=1
Answer: CNF: (A¬B¬C ∨ AB¬C ∨ ABC)
CNF allows logical functions to be represented in a
standardized form, simplifying their analysis and further processing.
Conjunctive Normal Form (CNF)
Imagine a
logical function as a puzzle where you need to assemble all the pieces to get
the correct answer. CNF is a way to rewrite the puzzle by dividing it into
blocks, where each block contains all the "cubes" (variables) in
different variations – as they are or flipped.
For example,
instead of "red or blue" in CNF, it would be "red AND blue"
or "not red AND not blue".
This way,
instead of a single complex task, you get a set of simpler ones, which helps
you understand the logical function step by step.
Stages of
CNF Construction
Let's try to understand
the logical expression using a table!
1)
Create a table
that lists all possible "inputs" (variable values) and their
corresponding "outputs" (the result of the logical expression).
2)
Highlight the
rows where the "output" is "false".
3)
For each such
row, write a "rule" that includes all the variables, but only those
that have a value of "true" in that row.
4)
Combine these
rules using "AND" to get an expression that is true only when all
rules are false.
Example 3:
Let's
consider the logical expression: A∧(B∨¬C).
Let's create
a table to illustrate how CNF is constructed.
|
A
|
B
|
C
|
¬C
|
B∨¬C
|
A∧(B∨¬C)
|
|
0
|
0
|
0
|
1
|
1
|
0
|
|
0
|
0
|
1
|
0
|
0
|
0
|
|
0
|
1
|
0
|
1
|
1
|
0
|
|
0
|
1
|
1
|
0
|
1
|
0
|
|
1
|
0
|
0
|
1
|
1
|
1
|
|
1
|
0
|
1
|
0
|
0
|
0
|
|
1
|
1
|
0
|
1
|
1
|
1
|
|
1
|
1
|
1
|
0
|
1
|
1
|
CNF is constructed based on the rows where the expression
is false (0)
Answer:
CNF: (A∨B∨C) ∧ (A∨B∨¬C) ∧ (A∨¬B∨C) ∧ (A∨¬B∨¬C) ∧ (¬A∨B∨¬C)
CNF is a
convenient way to represent logical functions because it allows for their
analysis and simplification.
Advantages and Applications of CNF and DNF
·
Standardization:
Both forms provide a standardized representation of logical functions,
simplifying their analysis and manipulation.
·
Simplified
Analysis: Converting logical expressions to CNF or DNF simplifies the processes
of verification and testing of logical circuits.
·
Universality:
These normal forms find applications in various fields, such as logical circuit
design, algorithm optimization, and cryptography tasks.
CNF and DNF
are essential tools in discrete mathematics, providing a structured and
understandable way to represent complex logical expressions.
Ru
Заключение
Совершенная
Конъюнктивная Нормальная Форма (СКНФ) и Совершенная Дизъюнктивная Нормальная
Форма (СДНФ) являются важными инструментами для представления и анализа
логических выражений. Они позволяют преобразовать сложные логические функции в
стандартные формы, что облегчает их анализ и последующую обработку. Таблицы
истинности служат фундаментом для построения этих нормальных форм, предоставляя
наглядный способ представления всех возможных комбинаций значений переменных и
соответствующих значений логического выражения.
En
Conclusion
Perfect
Conjunctive Normal Form (PCNF) and Perfect Disjunctive Normal Form (PDNF) are
important tools for representing and analyzing logical expressions. They allow
the transformation of complex logical functions into standard forms, which
facilitates their analysis and subsequent processing. Truth tables serve as the
foundation for constructing these normal forms, providing a visual way to
represent all possible combinations of variable values and their corresponding
truth values of the logical expression.
Использованная
Литература
1. Грэхем Р., Невзин Дж., Паташник О. Конкретная математика. Основы информатики. —
М.: Мир, 1998.
2. Кнут Д. Искусство программирования. Том 1. Основные
алгоритмы. — М.: Вильямс, 2011.
3. Мендельсон Э. Введение в математическую логику. — М.: Мир, 1976.
4. Липман Д., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.:
Вильямс, 2003.
5. Судоплатов С.В. Лекции по дискретной математике. — М.: МГУ, 2002.
© Гладких Д.В..,Исхаков М.А., 2024
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.