Как составить таблицу истинности для составного высказывания

Инфоурок

›

Информатика

›Презентации›Построение таблиц истинности для сложных высказываний.

Построение таблиц истинности для сложных высказываний.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Построение таблиц истинности

Екатерина Андреевна Гапонько

Эксперт по предмету «Информатика»

Задать вопрос автору статьи

Определение 1

Логическая функция – функция, переменные которой принимают одно из двух значений: $1$ или $0$.

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

Определение 2

Таблица истинности – таблица, которая показывает, какие значения примет составное выражение при всех возможных наборах значений простых выражений, входящих в него.

Определение 3

Равносильными называются логические выражения, последние столбцы таблиц истинности которых совпадают. Равносильность обозначается с помощью знака $«=»$.

Сдай на права пока
учишься в ВУЗе

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

Получить скидку 3 000 ₽

При составлении таблицы истинности важно учитывать следующий порядок выполнения логических операций:

Рисунок 1.

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

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

1. Определяют количество строк: кол-во строк = $2^n + 1$ (для строки заголовка), $n$ – количество простых выражений. Например, для функций двух переменных существует $2^2 = 4$ комбинации наборов значений переменных, для функций трех переменных – $2^3 = 8$ и т.д.

2. Определяют количество столбцов: кол-во столбцов = кол-во переменных + кол-во логических операций. При определении количества логических операций учитывают также порядок их выполнения.

3. Заполняют столбцы результатами выполнения логических операций в определенной последовательности, учитывая таблицы истинности основных логических операций.

«Построение таблиц истинности» 👇

Рисунок 2.

Пример 1

Составить таблицу истинности логического выражения $D=bar{A} vee (B vee C)$.

Решение:

1. Определим количество строк:

   Количество простых выражений – $n=3$, значит

   кол-во строк = $2^3 + 1=9$.

2. Определим количество столбцов:

   Количество переменных – $3$.

   Количество логических операций и их последовательность:

   1. инверсия ($bar{A}$);
   2. дизъюнкция, т.к. она находится в скобках ($B vee C$);

   3. дизъюнкция ($overline{A}vee left(Bvee Cright)$) – искомое логическое выражение.

      Кол-во столбцов = $3 + 3=6$.

3. Заполним таблицу, учитывая таблицы истинности логических операций.

Рисунок 3.

Пример 2

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

[F=overline{(Avee B)bigwedge overline{C}}vee overline{(Avee C)bigwedge B}]

Решение:

1. Определим количество строк:

   Количество простых выражений – $n=3$, значит

   кол-во строк = $2^3 + 1=9$.

2. Определим количество столбцов:

   Количество переменных – $3$.

   Количество логических операций и их последовательность:

   1. отрицание ($bar{C}$);
   2. дизъюнкция, т.к. она находится в скобках ($A vee B$);
   3. конъюнкция ($(Avee B)bigwedge overline{C}$);
   4. отрицание, которое обозначим $F_1$ ($overline{(Avee B)bigwedge overline{C}}$);
   5. дизъюнкция ($A vee C$);
   6. конъюнкция ($(Avee C)bigwedge B$);
   7. отрицание, которое обозначим $F_2$ ($overline{(Avee C)bigwedge B}$);

   8. дизъюнкция – искомая логическая функция ($overline{(Avee B)bigwedge overline{C}}vee overline{(Avee C)bigwedge B}$).

      Кол-во столбцов = $3 + 8 = 11$.

3. Заполним таблицу, учитывая таблицу истинности логических операций.

Рисунок 4.

Алгоритм построения логической функции по ее таблице истинности

1. Выделяют в таблице истинности строки со значением функции, равным $1$.
2. Выписывают искомую формулу как дизъюнкцию нескольких логических выражений. Количество этих выражений равно количеству выделенных строк.
3. Каждое логическое выражение в этой дизъюнкции записать как конъюнкцию аргументов функции.
4. В случае, когда значение какого-то из аргументов функции в соответствующей строке таблицы принимает значение $0$, то этот аргумент записать в виде его отрицания.

Пример 3

По данной таблице истинности некоторой логической функции $Y(A,B)$ cоставить соответствующую логическую функцию.

Рисунок 5.

Решение:

1. Значение функции равно $1$ в $1$-й и $3$-й строках таблицы.
2. Поскольку имеем $2$ строки, получим дизъюнкцию двух элементов:

   

   Рисунок 6.

3. Каждое логическое выражение в этой дизъюнкции запишем как конъюнкцию аргументов функции $A$ и $B$: $left(Awedge Bright)vee left(Awedge Bright)$
4. В случае, когда значение в соответствующей строке таблицы равно $0$, запишем этот аргумент с отрицанием, получим искомую функцию:[Yleft(A,Bright)=left(overline{A}wedge overline{B}right)vee left(Awedge overline{B}right).]

Находи статьи и создавай свой список литературы по ГОСТу

Поиск по теме

Дата написания статьи: 12.04.2016

Построение таблицы истинности. СДНФ. СКНФ. Полином Жегалкина.

Онлайн калькулятор позволяет быстро строить таблицу истинности для произвольной булевой функции или её вектора, рассчитывать совершенную дизъюнктивную и совершенную конъюнктивную нормальные формы, находить представление функции в виде полинома Жегалкина, строить карту Карно и классифицировать функцию по классам Поста.

Как пользоваться калькулятором

1. Введите в поле логическую функцию (например, x1 ∨ x2) или её вектор (например, 10110101)
2. Укажите действия, которые необходимо выполнить с помощью переключателей
3. Укажите, требуется ли вывод решения переключателем «С решением»
4. Нажмите на кнопку «Построить»

Видеоинструкция к калькулятору

Используемые символы

В качестве переменных используются буквы латинского и русского алфавитов (большие и маленькие), а также цифры, написанные после буквы (индекс переменной). Таким образом, именами переменных будут: a, x, a1, B, X, X1, Y1, A123 и так далее.

Для записи логических операций можно использовать
как обычные символы клавиатуры (*, +, !, ^, ->, =), так и символы, устоявшиеся в литературе (∧, ∨, ¬, ⊕, →, ≡). Если на вашей клавиатуре отсутствует нужный символ операции, то используйте клавиатуру калькулятора (если она не видна, нажмите «Показать клавиатуру»), в которой доступны как все логические операции, так и набор наиболее часто используемых переменных.

Для смены порядка выполнения операций используются круглые скобки ().

Обозначения логических операций

• И (AND): & • ∧ *
• ИЛИ (OR): ∨ +
• НЕ (NOT): ¬ !
• Исключающее ИЛИ (XOR): ⊕ ^
• Импликация: -> → =>
• Эквивалентность: = ~ ≡ <=>
• Штрих Шеффера: ↑ |
• Стрелка Пирса: ↓

Что умеет калькулятор

• Строить таблицу истинности по функции
• Строить таблицу истинности по двоичному вектору
• Строить совершенную конъюнктивную нормальную форму (СКНФ)
• Строить совершенную дизъюнктивную нормальную форму (СДНФ)
• Строить полином Жегалкина (методами Паскаля, треугольника, неопределённых коэффициентов)
• Определять принадлежность функции к каждому из пяти классов Поста
• Строить карту Карно
• Минимизировать ДНФ и КНФ
• Искать фиктивные переменные

Что такое булева функция

Булева функция f(x1, x2, ... xn) — это любая функция от n переменных x₁, x₂, … x_n, в которой её аргументы принимают одно из двух значений: либо 0, либо 1, и сама функция принимает значения 0 или 1. То есть это правило, по которому произвольному набору нулей и единиц ставится в соответствие значение 0 или 1. Подробнее про булевы функции можно посмотреть на Википедии.

Что такое таблица истинности?

Таблица истинности — это таблица, описывающая логическую функцию, а именно отражающую все значения функции при всех возможных значениях её аргументов. Таблица состоит из n+1 столбцов и 2n строк, где n — число используемых переменных. В первых n столбцах записываются всевозможные значения аргументов (переменных) функции, а в n+1-ом столбце записываются значения функции, которые она принимает на данном наборе аргументов.

Довольно часто встречается вариант таблицы, в которой число столбцов равно n + число используемых логических операций. В такой таблице также первые n столбцов заполнены наборами аргументов, а оставшиеся столбцы заполняются значениями подфункций, входящих в запись функции, что позволяет упростить расчёт конечного значения функции за счёт уже промежуточных вычислений.

Логические операции

Логическая операция — операция над высказываниями, позволяющая составлять новые высказывания путём соединения более простых. В качестве основных операций обычно называют конъюнкцию (∧ или &), дизъюнкцию (∨ или |), импликацию (→), отрицание (¬), эквивалентность (=), исключающее ИЛИ (⊕).

Таблица истинности логических операций

Как задать логическую функцию

Есть множество способов задать булеву функцию:

• таблица истинности
• характеристические множества
• вектор значений
• матрица Грея
• формулы

Рассмотрим некоторые из них:

Чтобы задать функцию через вектор значений необходимо записать вектор из 2ⁿ нулей и единиц, где n — число аргументов, от которых зависит функция. Например, функцию двух аргументов можно задать так: 0001 (операция И), 0111 (операция ИЛИ).

Чтобы задать функцию в виде формулы, необходимо записать математическое выражение, состоящее из аргументов функции и логических операций. Например, можно задать такую функцию: a∧b ∨ b∧c ∨ a∧c

Способы представления булевой функции

С помощью формул можно получать огромное количество разнообразных функций, причём с помощью разных формул можно получить одну и ту же функцию. Иногда бывает весьма полезно узнать, как построить ту или иную функцию, используя лишь небольшой набор заданных операций или используя как можно меньше произвольных операций. Рассмотрим основные способы задания булевых функций:

• Совершенная дизъюнктивная нормальная форма (СДНФ)
• Совершенная конъюнктивная нормальная форма (СКНФ)
• Алгебраическая нормальная форма (АНФ, полином Жегалкина)

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

Простая конъюнкция — это конъюнкция некоторого конечного набора переменных, или их отрицаний, причём каждая переменная встречается не более одного раза.
Дизъюнктивная нормальная форма (ДНФ) — это дизъюнкция простых конъюнкций.
Совершенная дизъюнктивная нормальная форма (СДНФ) — ДНФ относительно некоторого заданного конечного набора переменных, в каждую конъюнкцию которой входят все переменные данного набора.

Например, ДНФ является функция ¬abc ∨ ¬a¬bc ∨ ac, но не является СДНФ, так как в последней конъюнкции отсутствует переменная b.

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

Простая дизъюнкция — это дизъюнкция одной или нескольких переменных, или их отрицаний, причём каждая переменная входит в неё не более одного раза.
Конъюнктивная нормальная форма (КНФ) — это конъюнкция простых дизъюнкций.
Совершенная конъюнктивная нормальная форма (СКНФ) — КНФ относительно некоторого заданного конечного набора переменных, в каждую дизъюнкцию которой входят все переменные данного набора.

Например, КНФ является функция (a ∨ b) ∧ (a ∨ b ∨ c), но не является СДНФ, так как в первой дизъюнкции отсутствует переменная с.

Алгебраическая нормальная форма (АНФ, полином Жегалкина)

Алгебраическая нормальная форма, полином Жегалкина — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции, а в качестве сложения — исключающее ИЛИ.

Примеры полиномов Жегалкина: 1, a, a⊕b, ab⊕a⊕b⊕1

Алгоритм построения СДНФ для булевой функции

1. Построить таблицу истинности для функции
2. Найти все наборы аргументов, на которых функция принимает значение 1
3. Выписать простые конъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 0, то она входит в конъюнкцию с отрицанием, а иначе без отрицания
4. Объединить все простые конъюнкции с помощью дизъюнкции

Алгоритм построения СКНФ для булевой функции

1. Построить таблицу истинности для функции
2. Найти все наборы аргументов, на которых функция принимает значение 0
3. Выписать простые дизъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 1, то она входит в дизъюнкцию с отрицанием, а иначе без отрицания
4. Объединить все простые дизъюнкции с помощью конъюнкции

Алгоритм построения полинома Жегалкина булевой функции

Есть несколько методов построения полинома Жегалкина, в данной статье рассмотрим наиболее удобный и простой из всех.

1. Построить таблицу истинности для функции
2. Добавить новый столбец к таблице истинности и записать в 1, 3, 5… ячейки значения из тех же строк предыдущего столбца таблицы истинности, а к значениям в строках 2, 4, 6… прибавить по модулю два значения из соответственно 1, 3, 5… строк.
3. Добавить новый столбец к таблице истинности и переписать в новый столбец значения 1, 2, 5, 6, 9, 10… строк, а к 3, 4, 7, 8, 11, 12… строкам аналогично предыдущему пункту прибавить переписанные значения.
4. Повторить действия каждый раз увеличивая в два раза количество переносимых и складываемых элементов до тех пор, пока длина не станет равна числу строк таблицы.
5. Выписать булевы наборы, на которых значение последнего столбца равно единице
6. Записать вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора записать единицу) и объединить их с помощью операции исключающего ИЛИ.

Примеры построения различных представлений логических функций

Построим совершенные дизъюнктивную и дизъюнктивную нормальные формы, а также полином Жегалкина для функции трёх переменных F = ¬ab∨¬bc∨ca

1. Построим таблицу истинности для функции

---

Построение совершенной дизъюнктивной нормальной формы:

Найдём наборы, на которых функция принимает истинное значение: { 0, 0, 1 } { 0, 1, 0 } { 0, 1, 1 } { 1, 0, 1 } { 1, 1, 1 }

В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием:

K₁: { 0, 0, 1 } — ¬a¬bc
K₂: { 0, 1, 0 } — ¬ab¬c
K₃: { 0, 1, 1 } — ¬abc
K₄: { 1, 0, 1 } — a¬bc
K₅: { 1, 1, 1 } — abc

Объединим конъюнкции с помощью дизъюнкции и получим совершенную дизъюнктивную нормальную форму:

K₁ ∨ K₂ ∨ K₃ ∨ K₄ ∨ K₅ = ¬a¬bc ∨ ¬ab¬c ∨ ¬abc ∨ a¬bc ∨ abc

---

Построение совершенной конъюнктивной нормальной формы:

Найдём наборы, на которых функция принимает ложное значение: { 0, 0, 0 } { 1, 0, 0 } { 1, 1, 0 }

В соответствие найденным наборам поставим элементарные дизъюнкции по всем переменным, причём если переменная в наборе принимает значение 1, то она будет записана с отрицанием:

D₁: { 0, 0, 0 } — a∨b∨c
D₂: { 1, 0, 0 } — ¬a∨b∨c
D₃: { 1, 1, 0 } — ¬a∨¬b∨c

Объединим дизъюнкции с помощью конъюнкции и получим совершенную конъюнктивную нормальную форму:

D₁ ∧ D₂ ∧ D₃ = (a∨b∨c) ∧ (¬a∨b∨c) ∧ (¬a∨¬b∨c)

---

Построение полинома Жегалкина:

Добавим новый столбец к таблице истинности и запишем в 1, 3, 5 и 7 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 2, 4, 6 и 8 сложим по модулю два со значениями из соответственно 1, 3, 5 и 7 строк:

Добавим новый столбец к таблице истинности и запишем в 1 и 2, 5 и 6 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 3 и 4, 7 и 8 сложим по модулю два со значениями из соответственно 1 и 2, 5 и 6 строк:

Добавим новый столбец к таблице истинности и запишем в 1 2, 3 и 4 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 5, 6, 7 и 8 сложим по модулю два со значениями из соответственно 1, 2, 3 и 4 строк:

Окончательно получим такую таблицу:

Выпишем наборы, на которых получившийся вектор принимает единичное значение и запишем вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора следует записать единицу):

{ 0, 0, 1 } — c, { 0, 1, 0 } — b, { 0, 1, 1 } — bc, { 1, 1, 0 } — ab, { 1, 1, 1 } — abc

Объединяя полученные конъюнкции с помощью операции исключающего или, получим полином Жегалкина: c⊕b⊕bc⊕ab⊕abc

Департамент образования Ивановской области

ОГБПОУ «Кинешемский педколледж»

Построение таблиц истинности

Методическое пособие

Подготовила: Совина М.В.

преподаватель высшей категории

2015

М.В. Совина

Методическое пособие «Построение таблиц истинности»- Кинешма, 2015

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

Содержание

Алгебра логики…………………………………………………………………	4
Логические операции………………………………………………………….	5
Этапы построения таблиц истинности………………………………………	9
Пример построения таблиц истинности…………………………………….	10
Задания для самоконтроля……………………………………………………	12
Рекомендуемая литература……………………………………………………	13

Алгебра логики

Логика — это наука о формах и способах мышления. Логика позволяет строить формальные модели окружающего мира.

Первые учения о формах и способах рассуждений возникли
в странах Древнего Востока (Китай, Индия), но в основе
современной логики лежат учения, созданные древнегреческими
мыслителями.

Основными формами мышления являются: понятие, высказывание, умозаключение.

Понятие — это форма мышления, фиксирующая основные, существенные признаки объекта.

Высказывание — это форма мышления, в которой что-либо утверждается или отрицается о свойствах реальных предметов и отношениях между ними. Высказывание может быть либо ИСТИННО либо ЛОЖНО.

Умозаключение — это форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение

Основы формальной логики заложил Аристотель.

Алгебра логики была разработана для того, чтобы можно было
оперировать высказываниями, не вникая в их содержание.

Алгебра логики — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.

Создателем алгебры логики является живший в ХIХ веке английский математик Джордж Буль, в честь которого эта алгебра названа булевой алгеброй.

Логические операции

Простые высказывания обозначаются латинскими буквами: А, В, С …

Bысказывания, образованные из других высказываний с помощью логических связок, называются составными.

Употребляемые в обычной речи слова и словосочетания «не”, “и”, “или”, “если… , то”, “тогда и только тогда” и другие позволяют из простых высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение.

Пусть через А обозначено высказывание “Тимур поедет летом на море”,

а через В — высказывание “Тимур летом отправится в горы”.

А, В — логические переменные, каждое из которых мoжет принимать только два значения — “истина” или “ложь”, обозначаемые, соответственно, “1” или “0”.

Составное высказывание “Тимур летом побывает на море и в горах” можно кратко записать как А и В.

Здесь “и” — логическая связка.

Составное высказывание “Тимур летом побывает на море или в горах” можно кратко записать как А или В.

Здесь “или” — логическая связка.

Истинность или ложность получаемых составных высказываний зависит от истинности или ложности элементарных высказываний.

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

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

Приоритеты логических операций:

• инверсия (отрицание),

• конъюнкция (логическое умножение),

• дизъюнкция (логическое сложение),

• импликация (следование),

• эквивалентность (равносильность).

Изменить последовательность выполнения логических операций можно с помощью скобок.

Этапы построения таблиц истинности

Решение логических выражений принято записывать в виде таблиц истинности – таблиц, в которых по действиям показано, какие значения принимает логическое выражение при всех возможных наборах его переменных.

Для составления таблицы необходимо:

1. Выяснить количество строк в таблице. Оно равно 2ⁿ+1, где n-количество переменных.

2. Выяснить количество столбцов. Оно равно количество переменных плюс количество логических операций.

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

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

5. Заполнить таблицу истинности по столбцам.

Заполнение столбцов значений переменных таблицы:

1.  разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»;

2.  разделить колонку  значений  второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»;

3.  продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа.

Заполнение столбцов, содержащих логические операции, выполняется в соответствии с таблицами истинности этих логических операций

Примеры построения таблиц истинности

Пример 1. Для формулы  A/ (B / ¬B /¬C) постройте  таблицу истинности.

1этап:  Количество логических переменных 3, следовательно, количество строк — 2³ +1= 9.

2 этап: Количество логических операций в формуле 5, количество логических переменных 3, следовательно количество столбцов — 3 + 5 = 8.

3этап: Последовательность операций:

1) ¬B

2) ¬C

3)  ¬B /¬C

4) B / ¬B /¬C

5) A/ (B / ¬B /¬C)

4 этап: Построение таблицы

A	B	C	¬B	¬C	¬B¬C	B¬B¬C	A(B¬B¬C)

5 этап: Заполнение таблицы

 

Пример 2. Определите истинность  логического выражения  

F(А, В) = (А/ В)/(¬А/¬В) .

1. В выражении две переменные А и В (n=2).

2.  m_строк=2n, m=2²=4 строки.

3. В формуле 5 логических операций.

4. Расставляем порядок действий

1) А/ В;  2) ¬А;  3) ¬В;  4) ¬А/¬В;  5) (А/ В)/(¬А/¬В).

5. К_{столбцов}=n+5=2+5=7 столбцов.

А	В	А/ В	¬А	¬В	¬А/¬В	F
0	0	0	1	1	1	0
0	1	1	1	0	1	1
1	0	1	0	1	1	1
1	1	1	0	0	0	0

Вывод: логическое выражение принимает значение истина при наборах F(0,1)=1 и F(1,0)=1.

Задания для самоконтроля

1. Составьте таблицу истинности логического выражения:

A  B (A  B)

1. Определите истинность  логического выражения :

F(А,В) =A  B  C  A

1. Постройте таблицу истинности сложного высказывания

А V (A ^ B) V (B ^ C)

1. Составить таблицу истинности для формулы

X·Y v X v Y v X

1. Составить таблицу истинности для формулы

Рекомендуемая литература

1. Андреева Е.В. Математические основы информатики. Элективный курс: учебное пособие.-М.:БИНОМ. Лаборатория знаний, 2005

2. Выгодский М.Я. Справочник по элементарной математике. М. «Наука»,1989.

3. Соколова О.А. Универсальные поурочныеразработки по информатике 10 класс:- М.:ВАКО,2008, -400с.

4. Угринович Н. Информатика и ИТ 10-11- М.:Лаборатория Базовых Знаний,2001. – 464с.

5. Щеглов А.И. Элементарное введение в теорию множеств и алгебру логики. Иваново, 1978.

6. Математическая логика.- Режим доступа: // http://mathlog.h11.ru/index.html

7. Cистемa федеральных образовательных порталов . —

Режим лоступа: