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

Таблица истинности

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

Клавиша	Оператор
!	¬	Отрицание (НЕ)
|	|	Штрих Шеффера (И-НЕ)
#	↓	Стрелка Пирса (ИЛИ-НЕ)
*	&	Конъюнкция (И)
+	v	Дизъюнкция (ИЛИ)
^	⊕	Исключающее ИЛИ, сумма по модулю 2 (XOR)
@	→	Импликация (ЕСЛИ-ТО)
%	←	Обратная импликация
=	≡ (

, ↔) Эквивалентность (РАВНО)

bc необходимо ввести так: a*b*c+a*b=c+a=b*c
Для ввода данных в виде логической схемы используйте этот сервис.

Правила ввода логической функции

1. Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
2. Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
3. Максимальное количество переменных равно 10 .

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

Источник

Учитель информатики

Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.

Таблицы истинности

Информатика. 10 класса. Босова Л.Л. Оглавление

§ 19. Таблицы истинности

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

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

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

1) определить число строк таблицы m = 2 n , где n — число переменных в логическом выражении;
2) определить число столбцов таблицы как сумму чисел логических переменных и логических операций в логическом выражении;
3) установить последовательность выполнения логических операций с учётом скобок и приоритетов операций;
4) заполнить строку с заголовками столбцов таблицы истинности, занеся в неё имена логических переменных и номера выполняемых логических операций;
5) выписать наборы входных переменных с учётом того, что они представляют собой ряд целых n-разрядных двоичных чисел от 0 до 2 n — 1;
6) провести заполнение таблицы истинности по столбцам, выполняя логические операции.

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

В этом выражении две логические переменные и пять логических операций. Всего в таблице истинности будет пять строк (22 плюс строка заголовков) и 7 столбцов.

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

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

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

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

С помощью таблиц истинности докажите равносильность выражений

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

19.2. Анализ таблиц истинности

Рассмотрим несколько примеров.

Пример 2. Известен фрагмент таблицы истинности для логического выражения F, содержащего логические переменные А, В и С.

Сколько из приведённых ниже логических выражений соответствуют этому фрагменту?

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

1) Логическое выражение (A v С) & В соответствует данному фрагменту таблицы истинности:

2) Логическое выражение (A v В) & (С → А) не соответствует данному фрагменту таблицы истинности, т. к. уже на первом наборе значение рассматриваемого логического выражения не совпадает со значением F. Проведение дальнейших вычислений не имеет смысла.

3) Логическое выражение (А & В v С) & (В → А & С) не соответствует данному фрагменту таблицы истинности:

4) Логическое выражение (А → В) v (С v А → В) соответствует данному фрагменту таблицы истинности:

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

Можно ли утверждать, что в результате решения задачи мы нашли логическое выражение F?

Пример 3. Логическая функция F задаётся выражением:

Ниже приведён фрагмент таблицы истинности, содержащий все наборы переменных, на которых F истинна.

Определим, какому столбцу таблицы истинности функции F соответствует каждая из переменных х, y > z.

В исходном логическом выражении задействовано три логические переменные. Полная таблица истинности для этого выражения должна состоять из 8 (2 3 ) строк.

Наборам переменных, на которых логическое выражение истинно, соответствуют десятичные числа 0, 2, 3, 4 и 7.

Следовательно, наборам переменных, на которых логическое выражение ложно, должны соответствовать десятичные числа 1, 5 и 6 (их двоичные коды 001, 101 и 110). Построим по этим данным вторую часть таблицы истинности:

Теперь выясним, при каких значениях х, у, z логическое выражение ложно:

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

Первая дизъюнкция равна нулю на наборе 011. Для равенства нулю второй дизъюнкции требуется, чтобы х = 1, у = 0, а z может быть и 0, и 1.

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

Переменная у принимает единичное значение только один раз. Следовательно, ей соответствует второй столбец исходной таблицы. Из таблицы со значениями х, у и z следует, что при у = 1: х = 0, а z = 1. Следовательно, переменной z соответствует первый столбец, а переменной х — третий столбец исходной таблицы.

Убедиться в правильности полученного ответа можно, полностью заполнив следующую таблицу:

САМОЕ ГЛАВНОЕ

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

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

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

Вопросы и задания

1. Что представляет собой таблица истинности?

2. Составлена таблица истинности для логического выражения, содержащего n переменных. Известно m — количество строк, в которых выражение принимает значение 0. Требуется выяснить, в скольких случаях логическое выражение примет значение 1 при следующих значениях n и m:

1) n = 6, m = 15;
2) n = 7, m = 100;
3) n = 10, m = 500.

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

4. Рассмотрите два составных высказывания:

• F₁ = «Если одно слагаемое делится на 3 и сумма делится на 3, то и другое слагаемое делится на 3»;
• F₂ = «Если одно слагаемое делится на 3, а другое слагаемое не делится на 3, то сумма не делится на 3».

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

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

6. Какое из приведённых логических выражений равносильно выражению (А → С) & (B → С)?

1) А & В → С;
2) А → В → С;
3) A v Б → С;
4) А ↔ Б → С.

7. Известен фрагмент таблицы истинности для логического выражения F, содержащего логические переменные А, В и С.

Какое из приведённых далее логических выражений соответствуют этому фрагменту?

8. Логическая функция F задаётся выражением

Ниже приведён фрагмент таблицы истинности, содержащий все наборы переменных, на которых F ложна.

Какому столбцу таблицы истинности функции F соответствует каждая из переменных А, В, С?

Источник

Учитель информатики

Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.

Преобразование логических выражений

Информатика. 10 класса. Босова Л.Л. Оглавление

§ 20. Преобразование логических выражений

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

20.1. Основные законы алгебры логики.

Приведём основные законы алгебры логики.

1. Переместительные (коммутативные) законы:

2. Сочетательные (ассоциативные) законы:

(A v В) v С = A v (В v С).

3. Распределительные (дистрибутивные) законы:

A v (В & С) = (A v В) & (A v С).

4. Законы идемпотентности (отсутствия степеней и коэффициентов):

5. Закон противоречия:

6. Закон исключённого третьего:

7. Закон двойного отрицания:

8. Законы работы с константами:

A v 1 = 1; A v O = A;

9. Законы де Моргана:

10. Законы поглощения:

Справедливость законов можно доказать построением таблиц истинности.

Пример 1. Упростим логическое выражение

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

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

Аналогичные законы выполняются для операций объединения, пересечения и дополнения множеств. Например:

Пробуйте самостоятельно доказать один из этих законов с помощью кругов Эйлера.

Пример 3. На числовой прямой даны отрезки В = [2; 12] и С = [7; 18]. Каким должен быть отрезок А, чтобы предикат

становился истинным высказыванием при любых значениях х.

Преобразуем исходное выражение, избавившись от импликации:

причём это минимально возможное множество А.

Множество В — это отрезок [2; 12].

Изобразим это графически:

Пересечением этих множеств будет служить промежуток [2; 7[. В качестве ответа мы можем взять этот промежуток, а также любой другой, его включающий.

Чему равна минимальная длина отрезка А? Укажите ещё несколько вариантов множества А.

Пример 4. Для какого наименьшего неотрицательного целого десятичного числа а выражение

тождественно истинно (т. е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х)? Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.

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

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

Перепишем исходное выражение в наших обозначениях:

Рассмотрим предикат М(х) = (х & 28 ≠ 0). В числе 28 = 11100₂ 4-й, 3-й и 2-й биты содержат единицы, а 1-й и 0-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 4, 3 или 2 содержит единицу. Если и 4-й, и 3-й, и 2-й биты числа х нулевые, то высказывание х & 28 ≠ 0 будет ложным.

Рассмотрим предикат N(x) = (х & 45 ≠ 0). В числе 45 = 101101₂ 5-й, 3-й, 2-й и 0-й биты содержат единицы, 4-й и 1-й — нули.

Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 5, 3, 2 или 0 содержит единицу. Если и 5-й, и 3-й, и 2-й, и 0-й биты числа х нулевые, то высказывание х & 45 ≠ 0 будет ложным.

Рассмотрим предикат К(х) = (х & 17 = 0). В числе 17 = 10001₂ 3-й, 2-й и 1-й биты содержат нули, 4-й и 0-й — единицы. Побитовая конъюнкция 17 и х будет равна нулю, если в числе х 4-й и 0-й биты будут содержать нули. Множество истинности этого предиката — все х с нулями в 4-м и 0-м битах.

По условию задачи надо, чтобы

Запишем это выражение для рассмотренных множеств истинности:

Объединением множеств М и N являются все двоичные числа, у которых хотя бы один из битов с номерами 5, 4, 3, 2, 0 содержит единицу. Пересечением этого множества с множеством К будут все двоичные числа, у которых биты с номерами 4 и 0 будут заняты нулями, т. е. такие двоичные числа, у которых хотя бы один из битов с номерами 5, 3, 2 содержит 1. Все эти числа образуют множество А.

Искомое число а должно быть таким, чтобы при любом неотрицательном целом значении переменной х: х & а ≠ 0, и кроме того, оно должно быть минимальным из возможных. Этим условиям удовлетворяет число 101100₂. Действительно, единицы в нём стоят в тех и только в тех битах, которые нужны для выполнения условия х & а ≠ 0.

Итак, требуемое число 101100₂ или 44₁₀.

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

Пример 5. Выясним, сколько решений имеет следующая система из двух уравнений:

Конъюнкция истинна тогда и только тогда, когда истинны все образующие её высказывания. Следовательно, каждая из трёх входящих в конъюнкцию импликаций должна быть равна 1.

Начнем строить дерево решений, представив на нём значения переменных х₁ и х₂ при которых х₁ → х₂ = 1.

Продолжим строить дерево решений. Значения переменной х₃ будем выбирать такими, чтобы при имеющихся х₂ импликация х₂ → х₃ оставалась истинной.

То же самое проделаем для переменной х₄.

На дереве видно, что рассматриваемое нами уравнение имеет 5 решений — 5 разных наборов значений логических переменных x₁, х₂, х₃, х₄, при которых выполняется равенство:

Следовательно, как и первое уравнение, это уравнение имеет 5 решений. Представим их в табличной форме:

Решение исходной системы логических уравнений — это множество различных наборов значений логических переменных х₁, х₂, х₃, х₄, у₁, у₂, у₃, у₄ таких, что при подстановке каждого из них в систему оба уравнения превращаются в истинные равенства.

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

Всего мы можем построить 5 • 5 = 25 решений системы.

Вспомните, как называется теорема комбинаторики, которую мы применили для подсчёта количества решений системы.

20.2. Логические функции

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

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

Для n = 2 существует 16 различных логических функций.

Рассмотрим их подробнее.

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

1) F₂ и F₁₁ (конъюнкция и отрицание второго аргумента);

2) F₈ и F₁₃ (дизъюнкция и отрицание первого аргумента);

3) F₉ (стрелка Пирса, отрицание дизъюнкции);

4) F₁₅ (штрих Шеффера, отрицание конъюнкции).

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

20.3. Составление логического выражения по таблице истинности и его упрощение

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

Алгоритм составления логического выражения по таблице истинности достаточно прост. Для этого надо:

1) отметить в таблице истинности наборы переменных, при которых значение логического выражения равно единице;
2) для каждого отмеченного набора записать конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае — её отрицание;
3) все полученные конъюнкции связать операциями дизъюнкции.

Пример 6. Имеется следующая таблица истинности:

После выполнения двух первых шагов алгоритма получим:

После выполнения третьего шага получаем логическое выражение:

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

, а далее используем законы алгебры логики.

САМОЕ ГЛАВНОЕ

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

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

Для всякой таблицы истинности можно составить соответствующее ей логическое выражение.

Вопросы и задания

1. Какие из рассмотренных законов алгебры логики аналогичны законам алгебры чисел, а какие нет?

2. Докажите второй закон де Моргана с помощью таблиц истинности.

3. Путём преобразования докажите равносильность следующих высказываний:

4. Упростите логические формулы:

*5. Найдите X,

6. На числовой прямой даны два отрезка: Р = [10; 25] и Q = [20; 55]. Укажите наибольшую возможную длину такого отрезка А, что выражение (х ∈ А) → ((х ∈ Р) v (x ∈ Q)) истинно при любом значении переменной х.

7. Элементами множеств А, Р и Q являются натуральные числа, причём Р = <2, 4, 6, 8, 10, 12>и Q = <2, 6, 12, 18, 24>.

Известно, что выражение

истинно при любом значении переменной х. Определите наименьшее возможное количество элементов множества А.

*8. На числовой прямой даны два отрезка: М = [10; 60] и N = [40; 80]. Укажите наименьшую возможную длину такого отрезка А, что выражение

истинно при любом значении переменной х.

9. Для какого наименьшего неотрицательного целого десятичного числа А формула x & 25 ≠ 0 → (x & 17 = 0 → (x & А ≠ 0) тождественно истинна, т. е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х? (Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.)

*10. Определите наибольшее натуральное десятичное число А, при котором выражение ((x & 46 = 0) v (х & 18 = 0)) → ((х & 115 ≠ 0) v (х & А = 0)) тождественно истинно, т. е. принимает значение 1 при любом натуральном значении десятичной переменной х. (Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.)

11. Сколько различных решений имеет система уравнений:

12. Сколько существует различных логических функций от четырёх переменных?

13. По заданной таблице истинности составьте логические выражения для функций F₁, F₂.

14. По известным таблицам истинности запишите аналитическое представление импликации, эквиваленции и строгой дизъюнкции.

15. Логические функции штрих Шеффера и стрелка Пирса названы так в честь математиков, исследовавших их свойства. Подготовьте краткую биографическую справку об одном из этих учёных.

16. По заданной таблице истинности составьте логические выражения для функций F₁, F₂.

17. Запишите логическое выражение для логической функции F(A, В, С), равной 1 на наборах 011, 101, 110, 111. Попытайтесь упростить полученное выражение.

Оглавление

§ 20. Преобразование логических выражений

Источник