Таблицы истинности и их построение. СКНФ И СДНФ

Гладких Д.В,

студ. ГБПОУ НМК,

М.А. Исхаков,

Преподаватель

Аннотация: Дискретная математика имеет значительное значение в ряде

научных и технических областей, таких как информатика, криптография и

алгоритмы. Логические выражения и их нормальные формы занимают

центральное место среди ключевых понятий данной дисциплины. Совершенная

конъюнктивная нормальная форма (СКНФ) и совершенная дизъюнктивная

нормальная форма (СДНФ) являются ключевыми способами представления

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

истинности, а также детально проанализируем СКНФ и СДНФ на конкретных

примерах.

Ключевые слова: Дискретная математика, алгоритмы, СКНФ, СДНФ.

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 ex-

pressions 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 exam-

ples.

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

(А ∨ B) →

(¬A)

Пояснение решения

Давайте разберем логику шаг за шагом для первой строки, где A = 0 и B =

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).

Давайте создадим таблицу, которая покажет нам, как работает построение

СДНФ.

¬C

B∨¬C

A∧(B∨¬C)

СДНФ составляется по строкам, где выражение истинно (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).

Давайте создадим таблицу, которая покажет нам, как работает построение

СКНФ.

¬C

B∨¬C

A∧(B∨¬C)

СКНФ составляется по строкам, где выражение ложно (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

(А ∨ B) →

(¬A)

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 re-

sult 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 implica-

tion is true (1).

Conjunctive Normal Form (CNF)

Imagine a logical function like a recipe, where each line represents a set of in-

gredients, 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 varia-

tions – 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.

¬C

B∨¬C

A∧(B∨¬C)

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, simplify-

ing 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.

¬C

B∨¬C

A∧(B∨¬C)

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 struc-

tured and understandable way to represent complex logical expressions.

Заключение

Совершенная Конъюнктивная Нормальная Форма (СКНФ) и Совершенная

Дизъюнктивная Нормальная Форма (СДНФ) являются важными

инструментами для представления и анализа логических выражений. Они

позволяют преобразовать сложные логические функции в стандартные

формы, что облегчает их анализ и последующую обработку. Таблицы

истинности служат фундаментом для построения этих нормальных форм,

предоставляя наглядный способ представления всех возможных

комбинаций значений переменных и соответствующих значений

логического выражения.

Conclusion

Perfect Conjunctive Normal Form (PCNF) and Perfect Disjunctive Normal

Form (PDNF) are important tools for representing and analyzing logical ex-

pressions. 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.

Скачать материал

Таблицы истинности и их построение. СКНФ И СДНФ

Педагогика - еще материалы к урокам:

Предметы

Похожие материалы