Как составить таблицу истинности по уравнению

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

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

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

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

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

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

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

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

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

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

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

Сделаем домашку
с вашим ребенком за 380 ₽

Уделите время себе, а мы сделаем всю домашку с вашим ребенком в режиме online

Бесплатное пробное занятие

*количество мест ограничено

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

Рисунок 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

0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

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

Для данного примера

коньюнкция этих дизъюнкций и будет
искомой формулой:

Определение:Конъюнкция
называетсяэлементарной, если
все переменные, входящие в нее, различны.
Количество букв, входящих в элементарную
конъюнкцию или элементарную дизъюнкцию,
называетсярангом.

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

Строго доказано, что любую формулу
булевой алгебры можно выразить с помощью
операций , &,.
Интуитивно этот факт очевиден, вспомним
алгоритм составления формулы по таблице
истинности. При этом мы используем
только эти операции. Такая форма записи
называетсядизъюнктивной нормальной
формой(ДНФ). Это своеобразный механизм
нормализации формул алгебры логики.

Определение:ДНФ– это
дизъюнкция различных элементарных
конъюнкций (т.е. каждая конъюнкция
состоит из элементарных высказываний
или их отрицаний).

Аналогично определяется КНФ – коньюктивная
нормальная форма.

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

Теорема. Для любой функции, не
являющейся тождественно ложной,
существует и притом единственная СДНФ.

Следствие. Любую булеву функцию,
не являющуюся тождественно ложной можно
представить в виде суперпозиции&,,,
причем отрицание относится только к
переменным.

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

Системы {&,,};
{,};
{&,},{/}
– являются функционально полными

{&,}
– функционально неполная.

Мы примем эти факты без доказательства,
и решая задачи, будем стараться любую
формулу представить с помощью {&,,}.
Позже мы более подробно обсудим вопрос
функциональной полноты и неполноты
системы операций.

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

Рассмотрим пример решения логической
задачи.

Пример:

После обсуждения состава участников
экспедиции решено, что должны выполняться
два условия.

1. Если поедет Арбузов, то должны ехать
   Брюквин или Вишневский

2. Если поедут Арбузов и Вишневский то
   поедет Брюквин

Составить логическую формулу принятия
решения в символической форме, упростить
полученную формулу и сформулировать
по ней новое условие формирования
экспедиции.

Введём переменные и соответствующие
им элементарные высказывания.

– поедет Арбузов

– поедет Брюквин

– поедет Вишневский

Тогда выработанные условия формирования
экспедиции будут выглядеть следующим
образом:

1. 

2. 

Составим общую формулу и упростим
выражение

т.е. если поедет Арбузов, то поедет
Брюквин.

Пример:

Если завтра будет хорошая погода, то мы
пойдем на пляж или поедем в лес. Составим
формулу нашего поведения на завтра.

–
хорошая погода

– мы пойдем на пляж

– мы поедем в лес

Теперь построим отрицание этой фразы

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

Желающие могут построить таблицу
истинности и проверить это утверждение.

Пример:

По подозрению в совершенном преступлении,
задержаны Браун, Джон и Смит. Один из
них уважаемый в городе старик, второй
чиновник, а третий известный мошенник.
В ходе следствия старик говорил правду,
мошенник лгал, а третий задержанный в
одном случае говорил правду, а в другом
лгал.

Вот что они говорили:

Браун: Я совершил это. Джон не виноват.
(Б&Д)

Джон: Браун не виноват. Преступник Смит.
(Б&С)

Смит: Я не виноват. Виноват Браун (С&Б)

Опишем эти высказывания формально:

– преступление совершил Браун

– преступление совершил Джон

– преступление совершил Смит

Тогда их слова описываются следующими
выражениями:

Браун:

Джон:

Смит:

Т.к. по условиям задачи две из этих &ложны и одна истинна, то

Составим таблицу истинности

NN
1	0	0	0	0	0	0	0
2	0	0	1	0	1	0	1
3	0	1	0	0	0	0	0
4	0	1	1	0	1	0	1
5	1	0	0	1	0	1	1
6	1	0	1	1	0	0	1
7	1	1	0	0	0	1	1
8	1	1	1	0	0	0	0

1. Исключим из рассмотрения те наборы, на
   которых
   (по условию задачи одна из&- истинна, следовательно,)
   1, 3, 8

2. Исключим случай 5, т.к. в нем две &истинны, что противоречит условию
   задачи.

3. В случаях 4, 6, 7 у нас в начальном наборе
   две 1 , т.е. 2 преступника, а по условию
   задачи он один.

Остается только случай 2 , т.е. преступник
Смит, и оба его высказывания ложны.

следовательно–
ложно и–
истинно

=
1 – Джон уважаемый старик

Остается, что Браун чиновник, и поскольку
– ложно , то– истинно.

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

Пример:

Упражнение:

(X&Y&Z)(X&Y&Z)X&Y

Соседние файлы в папке Коспект лекций

• #

  16.03.2016266 б10desktop.ini

• #

  16.03.201611.67 Кб10Folder.htt

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

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

Шаги по созданию таблицы истинности

• Перечислите все предложения в высказываниях.

 Составление списков. Например, (A и B) или (не C) пропозициями являются A, B и C.

• Определите количество строк

Оно равно 2n, где n — количество предложений в выражении. В нашем примере есть три предложения (A, B и C), поэтому число строк будет равно 2 3 = 8.

• Перечислите все возможные итоги истинности

На этом этапе необходимо перечислить все исходы значений истинности для утверждений внутри выражения. Например, в нашем примере с тремя предложениями (A, B и C) бывает 8 исходов.

• Вычислите значения для всего

В промежутке узнать значение для каждого строкового данного. Для этого вам нужно подставить результаты для предложений в выражении и вычислить пример.

Полезные советы

Начните с простых выражений

Если вы новичок, рекомендуется начать с простых примеров, содержащих только одно или два предложения. Это поможет вам понять, как работают таблицы истинности, прежде чем переходить к более сложным примерам.

Используйте согласованный порядок для предложений

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

Используйте таблицу истинности. Для упрощения

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

Расширенные концепции в таблицах истинности

Как только вы освоите основы таблиц истинности, вы можете перейти к сложным концепциям. Вот несколько примеров:

• Отрицание (Инверсия)

Отрицание — это логический оператор, который изменяет смысл предложения на противоположное. В таблице истинности отрицание может быть представлено символом «не» (~).  

• Конъюнкция

Это оператор, может быть представлен знаком «и» (&).

• Дизъюнкция

Это оператор, представляющий «или». Она может быть представлена символом «или» (|). 

• Условный

Это оператор, который представляет «если-то». В таблице условное обозначение может быть представлено символом стрелки (->).

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

План урока:

Способы решению задач по логике

Табличный способ – этапы, особенности

Сравнение методов решения

Построение таблиц истинности для различных типов задач

Построение электрических схем, реализующих логические операции

Способы решения задач по логике

Многие задачи можно решить, используя инструменты алгебры логики. Чтобы получить результат, можно пойти 3 путями:

• рассуждая над условием;
• решая логические операции;
• используя таблицы истинности.

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

Этапы решения логических задач:

• Разобраться с условием на естественном языке, выделив простые высказывания, и дать им символьные обозначения (латиница).
• Записать условие в виде формулы. Решить ее поэтапно, упрощая, учитывая приоритеты (( ), ¬, &, V).
• Просчитать формулы строчно или при помощи таблиц истинности, учитывая законы алгебры логики.
• Проверить, соответствует ли полученный результат условию задачи.

Табличный способ – этапы, особенности

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

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

Метод таблиц

Чтобы использовать таблицы истинности, необходимо формализовать условие, то есть отойти от деталей задачи, обозначая первоначальную информацию при помощи букв и цифр 0 и 1.

Существует общий алгоритм построения таблиц:

• Определить число логических значений/переменных (n) в примере.
• Установить вид, число и тип операций. Важно заранее определить очередность действий, выразить это при помощи скобок.
• Полученные данные позволяют рассчитать сколько нужно столбцов – это сумма числа переменных и операций.
• Нарисовать таблицу, заполнить шапку, записав обозначение переменных и выбранные действия.
• Определить, сколько существует наборов логических переменных (т.е. число строчек) по формуле m = 2ⁿ+ 1 (шапка).
• Заполнить столбцы, вписав наборы значений логических переменных (0 или 1).
• Записать результаты логических операций, указанных в шапке для каждой совокупности значений.
• Сделать выводы на основании полученных результатов.

Если необходимо перебрать все значения простых выражений, то для задач:

• с 2-мя переменными может быть только 4 набора логических переменных;

Если словесно описывать все эти комбинаций, на каждый из примеров понадобится десятки строк текста.

 Обязательно учитывают приоритет операций:

• Указанные в скобках.
• Отрицание.
• Логическая конъюнкция чисел.
• Дизъюнкция.
• Строгая дизъюнкция.
• Импликация.
• Эквивалентность.

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

Сравнение методов решения

Метод рассуждений

Он заключается в пошаговом анализе условий с промежуточными выводами на каждом этапе. Выполняется анализ таблицы истинности каждого логического выражения.

Пример №1.

Андрей, Владимир, Георгий и Дмитрий живут на одной улице, они соседи. Они работают по таким специальностям: гитарист, плотник, егерь и стоматолог.

Известно, что:

• дом плотника правее егеря;
• стоматолог проживает левее егеря;
• дом гитариста с самого краю;
• стоматолог живет рядом с гитаристом;
• Владимир не гитарист, и его дом не соседствует с гитаристом;
• дома Дмитрия и егеря соседние;
• здание, в котором прописан Андрей, правее стоматолога;
• между домами Андрея и Дмитрия один дом.

Чтобы рассуждать было проще, добавим изображение зданий, присвоим им номера:

Но стоматолог живет левее егеря, а правее егеря – плотник. Получается, что дом гитариста не может быть последним, а дом стоматолога не может быть предпоследними. То есть, егерь живет в предпоследнем доме:

Между домами Андрея и Дмитрия стоит один дом, значит, дом Андрея не может быть предпоследним, получается номер – 4, что автоматом исключает проживание там Дмитрия и Владимира.

Условие задачи заняло 2 предложения, а рассуждений получилось на 2 страницы.

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

Табличный метод

Более удачным подходом к решению задач с большим количеством данных (несколько множеств), считается табличный, или графический (диаграммы).

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

• Разбить задачу на простейшие утверждения, которые обозначить символами (большие буквы латинского алфавита).
• Записать условие задачи, как составное выражение из символов логических операций.
• Нарисовать таблицу истинности для полученных данных.
• Выбрать такой вариант, при котором полученные значения подходят под условие.
• Проверить соответствие выбранного варианта и условия задачи.

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

Рассмотрим тот же пример.

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

Метод компактнее, для некоторых задач нагляднее.

Построение таблиц истинности для различных типов задач

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

Пример 2.

Известно, что если первый студент летал в Англию на стажировку, то и второй тоже летал, но неправда, что если летал третий, то и второй.

Разобьём условие на 3 простые высказывания, присвоим им буквенные обозначения:

А — «Первый студент летал в Англию»;

В — «Второй студент летал в Англию»;

С — «Третий студент летал в Англию».

Запишем выясненные данные при помощи логических операций:

Пример 3.

Есть три 8-ых класса (А, В, С), которые соревнуются между собой за средний бал. Учителя в начале года сделали такие предположения:

• Если А получит максимальный бал, то максимальный бал получат Ви С.
• А и С получат или не получат максимальный бал одновременно.
• Необходимым условием получения высшего бала С класса является получение высшего бала В классом.

По завершении года оказалось, что 2 предсказания оказались верными, а одно – ошибочным.

Выясним, какие же классы добились высшего бала.

Разбиваем условие задачи на элементарные высказывания:

А – «А добьется высшего бала»;

В – «В добьется высшего бала»;

С – «С добьется высшего бала».

Запишем логические операции, описанные в примере:

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

Пример 4.

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

• последняя – гласная (Х1);
• или первая буква согласная (Х2)
• вторая – согласная (Х3).

¬(Х1→Х2)VХ3

Предложенные имена: Арина, Артур, Кэтрин, София.

Решим задачу, используя таблицу.

Сначала решим пошагово, выполняя операции по приоритету:

Указанному условию соответствует первое имя.

Пример 5.

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

Известно, что в олимпиаде по химии участвовали 4 ученицы 8 класса: Марина, Света, Саша и Галя. Они заняли первые 4 места. Какое место заняла каждая из девочек, если есть их высказывания о победителях, но в них лишь половина информации правдива – первая или вторая половина предложения.

Маша Марина: «Саша заняла второе место, а Света – первое».

Полина Света: «Нет, это не так, Саша – победительница, а Галя, – на втором месте».

Ольга Саша: «Зачем вы всех путаете? Третье место за Мариной, а Света – на четвертом месте».

Составляем таблица для перебора вариантов. Правду обозначаем «1», ложь – «0».

Берем любое (Марины) утверждение и принимаем его первую часть за правду. Значит, Саша – 2 место, тогда Света не 1-ое (вторая половина фразы – ложь), остальных девочек на 2 место ставим «0».

Берем утверждение второй девочки. Так как Саша не может быть победительницей, то в этой фразе первая часть – ложь, а вторая должна быть истинной. Но в нем и вторая часть – неверна (второе место за Сашей, мы так приняли в начале).Уже на второй фразе получается противоречие всему.

Итог: Победительницей олимпиады стала Светлана, на втором месте – Галина, на третьем – Марина, на последнем из четырех – Александра.

 Построение электронных схем, реализующих логические операции

Если рассмотреть электросхемы с точки зрения логики, особенно компьютерные, то их также можно описать при помощи «1» и «0» – электричество идет или не идет по проводам.

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

Электросхема с конъюнктором

 Рассмотрим все варианты:

• Все контакты включены, тогда источник света горит.
• Первый контакт в положении «выключено» – свет не горит.
• Второй контакт выключен – лампа не светит.
• Все контакты отключены – свет не горит.

Заключение – эта электрическая цепь реализует операцию «И».

Дизъюнктор, схема электропитания

Рассмотрим этот вид электрической цепочки:

• Все контакты включены – лампа горит.
• Первый контакт включен, второй выключен – свет горит.
• Обратная ситуация – выключен первый, включен второй – лампа светится.
• Все контакты выключены – света нет.

Заключение – такой вид электросхем соответствует логической операции «ИЛИ».

Инвертор в электросхемах

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

Заключение: схема соответствует логической операции «НЕ».

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

Обозначение логических элементов

Удобно создавать электросхемы в ПО SmartNotebook, которое используется с интерактивной доской.