Меню

Дан фрагмент таблицы истинности выражения F



ЕГЭ по информатике — Задание 2 (Мощнейший метод)

Здравствуйте, дорогие друзья! Сегодня разберём, как решать второе задание из ЕГЭ по информатике 2020.

Во втором задании ЕГЭ по информатике у нас обычно есть логическая функция, которая зависит от логических переменных. Логические переменные могут принимать только два значения: 0 (Ложь) или 1 (Истина).

ЕГЭ по информатике - задание 2 (Логические функции и переменные)

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

ЕГЭ по информатике - задание 2 (Логическое отрицание)

ЕГЭ по информатике - задание 2 (Логическое сложение)

ЕГЭ по информатике - задание 2 (Логическое умножение)

ЕГЭ по информатике - задание 2 (Логическое следование)

ЕГЭ по информатике - задание 2 (логическая равносильность)

ЕГЭ по информатике - задание 2 ( 2 задание сложение по модулю 2)

ЕГЭ по информатике - задание 2 ( логические формулы)

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

  1. () — операции в скобках
  2. ¬ — логическое отрицание
  3. ∧ — логическое умножение
  4. ∨ — логическое сложение
  5. ⟶ — следование
  6. ≡ — равнозначность

Так же на ЕГЭ по информатике будет полезно знать логические формулы :

ЕГЭ по информатике - задание 2 ( интересные формулы)

Ещё соотношения:

Передём к решению задач из ЕГЭ по информатике

Логическая функция F задаётся выражением z ∧ ¬y ∧ (w → x). Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

ЕГЭ по информатике - задание 2 (лёгкая задача)
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно. Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
ЕГЭ по информатике - задание 2 (лёгкая задача) пример
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

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

ЕГЭ по информатике - решение лёгкой задачи

Отсюда видно, что переменная z должна всегда быть равна 1 (единице). Это первый столбец. Отрицание y тоже должно быть 1 (единицей), тогда просто y всегда будет 0 (нулём). Это второй столбец.

Осталось определить положение w и x. Здесь делаем предположение, что в третьем столбце стоит w, а в 4-ом x. Проверяем построчно и видим, что во второй строчке при таком расположении из 1 следует 0, что в итоге приводит выражение (w → x) в 0, а у нас это выражение всегда должно быть 1 (единицей). Значит, мы предположение сделали неверное, и получается x — это третий столбец, а w — четвёртый.

Задача 2 (средний уровень)

Логическая функция F задаётся выражением (x ∧ ¬y) ∨ (y ≡ z) ∨ w.
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

ЕГЭ по информатике - задание 2 (задача)

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

ЕГЭ по информатике - задание 2 (лёгкая задача) пример

Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

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

Во всех строчках таблицы функция принимает значение 0 (ноль). Значит, и каждое выражение должно принимать значение 0 (ноль).

ЕГЭ по информатике - задание 2 (задача схема) пример

Самым слабым звеном является переменная w, потому что она стоит одна. Переменная w должна равняться всегда 0(нулю) — этому условию может удовлетворить только третий столбец. Значит w стоит на третьем месте.

Следующим слабым звеном является равносильность. Она должна «выдавать» 0 (ноль). Равносильность «выдаёт» 0 (ноль), когда переменные разные!

Проанализируем первый и второй столбец. В третьей строчке, и там, и там, стоит 1 (единица). Значит, первый и второй столбец не могут быть одновременно y и z (или z и y).

Рассмотрим второй и четвёртый столбец. Вторая строчка содержит одинаковое значение 0 (ноль), и там, и там. Значит, второй и четвёртый столбец не могут быть одновременно y и z (или z и y).

Таким образом, y и z (или z и y) будут столбцы первый и четвёртый! И теперь можно расставить недостающие значения в этих столбцах. Расставляем, чтобы были разные значения, а второй столбец получается x.

ЕГЭ по информатике - задание 2 (решение) пример

Осталось разобраться с z и y. Обратимся к первому выражению (x ∧ ¬y) и посмотрим на третью строчку. Если в четвёртом столбце будет стоять y, то отрицание на y превратит ноль(ноль) в 1(единицу) в четвёртой строчке. Тогда окажется, что у x — 1 и ¬y — 1, и выражение (x ∧ ¬y) тоже получится 1(единицей). А у нас каждое выражение должно равняться 0(нулю). Получается y будет стоять в первом столбце, а z в четвёртом.

Тогда ответ будет равен yxwz.

Ответ: yxwz

Мощнейший метод для решения второго задания из ЕГЭ по информатике

Задача 3 (хороший уровень)
Логическая функция F задаётся выражением ((x → y ) ∧ (y → w)) ∨ (z ≡ ( x ∨ y)).
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

ЕГЭ по информатике - задание 2 мощнейший метод
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
ЕГЭ по информатике - задание 2 (лёгкая задача) пример
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.

«Главной скрипкой» в нашей функции является логическое сложение, потому что соединяет два выражения ((x → y ) ∧ (y → w)) и (z ≡ ( x ∨ y)).

Тогда каждое выражение должно равняться 0(нулю).

ЕГЭ по информатике - решение второго задания мощнейшим методом

Теперь кульминация мощнейшего метода. У нас всего 4 переменных. Выпишем все комбинации для 4-х переменных. Таблица будет точно такая же, как мы писали в первом задании (её очень легко составить). Всего получается 16 комбинаций (16 = 2 4 ).

Читайте также:  Томас Мор Утопия краткое содержание с цитатами

Теперь отметим зелёным плюсом те строчки, которые обращают выражение ((x → y ) ∧ (y → w)) в 0(ноль). Следующий шаг: Отметим галочкой те строчки, которые обращают в ноль второе выражение (z ≡ ( x ∨ y)) (Мы должны искать среди тех, которые уже отмечены плюсом).

При небольшой тренировке анализ подобных выражений занимает сущие секунды!

ЕГЭ по информатике - решение второго мощнейший метод (перебор)

У нас получается 4 строчки, которые удовлетворяют нашей функции:

ЕГЭ по информатике - решение второго задания мощнейший метод (финал)

Отсюда видно, что переменная z может быть равна только 0(нулю)! Значит, она занимает третий столбец, потому что в остальных столбцах есть хотя бы одна 1(единица).

Переменная w имеет только одну 1(единицу). Значит, её ставим во второй столбец, потому что в первом и четвёртом уже по 2 единицы минимум, а третий уже занят z.

Теперь находим строчку c 1(единицей) в переменной w (Таблица данная в условии задачи) Кто в этой строчке будет иметь единицу (кроме w) — будет x! Это четвёртый столбец! Значит, x — это четвёртый столбец. Переменной y — достаётся первый столбец

Ответ: ywzx.

На этом всё! Сегодня рассмотрели теорию и основные методы для эффективного решения второго задания из ЕГЭ по информатике!

Пока!

Источник

Презентация«Подготовка к ЕГЭ Задача А3,А10,В12,B15»

Логические задачи Подготовка к ЕГЭ Задача А3,А10,В12,B15 Автор: Керженова М.З.

Описание презентации по отдельным слайдам:

Логические задачи Подготовка к ЕГЭ Задача А3,А10,В12,B15 Автор: Керженова М.З.

Содержание План подготовки к ЕГЭ Базовые знания по теме «Логика» Методика решения некоторых логических задач Дополнительная литература и сайты по теме ЕГЭ

Основные знания по теме «Логика» Базовые логические операции НЕ, И, ИЛИ Дополнительные логические операции Исключающее ИЛИ Импликация Эквивалентность

Основные знания по теме «Логика»

Приоритет логических операций : вычисление в скобках НЕ, И, ИЛИ, исключающее ИЛИ импликация эквивалентность Основные знания по теме «Логика» Замена операций    через И, ИЛИ и НЕ: Формулы де Моргана:

Построение таблиц истинности логических выражений* Разбор задачи A3 Задание А3. Задача. Дан фрагмент таблицы истинности выражения F. Какое выражение соответствует F? 1) (X  Y)  ¬Z 2) ¬X  Y  Z 3) X  Y  ¬Z 4) X  ¬Y  Z X Y Z F 1 0 0 1 1 0 1 0 1 1 1 0 0 1 0 1

Решение: нужно для каждой строчки подставить заданные значения X, Y и Z во все функции, заданные в ответах, и сравнить результаты с соответствующими значениями F для этих данных если для какой-нибудь комбинации X, Y и Z результат не совпадает с соответствующим значением F, оставшиеся строчки можно не рассматривать, поскольку для правильного ответа все три результата должны совпасть со значениями функции F Из полученной таблицы видно, что F соответствует выражение 1: (X  Y)  ¬Z (выделено зеленым). Значения остальных выражений не совпадают с F (выделено розовым). X Y Z (X  Y)  ¬Z ¬X  Y  Z X  Y  ¬Z X  ¬Y  Z F 1 0 0 (1  0)  ¬0=1 ¬1  0  0=0 1 0  ¬0=0 1 ¬0  0=1 1 1 0 1 (1  0)  ¬1=0 ¬1  0  1=1 1  0  ¬1=0 1  ¬0  1=1 0 1 1 1 (1  1)  ¬1=0 ¬1  1  1=1 1  1  ¬1=0 1  ¬1  1=1 0 0 1 0 (0 1)  ¬0=1 ¬0  1  0=1 0  1  ¬0=0 0  ¬1  0=0 1

Каким из приведённых ниже выражений может быть F? ¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7 ¬x1 \/ x2 \/ ¬x3 \/ x4 \/ ¬x5 \/ ¬x6 \/ x7 x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7 x1 \/ ¬x2 \/ x3 \/ ¬x4 \/ ¬x5 \/ x6 \/ ¬x7 Дан фрагмент таблицы истинности выражения F. Разбор задачи A3 Построение таблиц истинности логических выражений* № области x1 x2 x3 x4 x5 x6 x7 F 1 1 1 0 1 1 1 1 0 2 1 0 1 0 1 1 0 0 3 0 1 0 1 1 0 0 1

Решение: Сначала определим, как связаны переменные в F: с помощью конъюнкции (Λ) или дизъюнкции (V). Если выражение содержит только конъюнкции, то оно может быть истинно только на одной области. В данном случае F истинна (равна 1) на одной области (область №3 в таблице выше), поэтому начнем с проверки выражений, содержащих конъюнкции. Это вариант 1 и вариант 3. Получили вариант 1: ¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7 x1 x2 x3 x4 x5 x6 x7 F F=¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7 (вариант 1) F=x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7 (вариант 3) 1 1 0 1 1 1 1 0 0Λ1Λ1Λ1Λ1Λ0Λ0=0 1Λ0Λ0Λ0Λ1Λ1Λ0=0 1 0 1 0 1 1 0 0 0Λ0Λ0Λ0Λ1Λ0Λ1=0 1Λ1Λ1Λ1Λ1Λ1Λ1=1 0 1 0 1 1 0 0 1 1Λ1Λ1Λ1Λ1Λ1Λ1=1

Разбор задачи A10 На числовой прямой даны два отрезка: P = [2, 10] и Q = [6, 14]. Выберите такой отрезок A, что формула ( (x ∈ А) → (x ∈ P) ) \/ (x ∈ Q) тождественно истинна, то есть принимает значение 1 при любом значении переменной х. [0, 3] [3, 11] [11, 15] [15, 17]

Решим уравнение: ( (x ∈ А) → (x ∈ P) ) \/ (x ∈ Q)=1 методом подстановки. В уравнение вместо P, Q впишем сами отрезки: [2, 10] и [6, 14]. (x ∈ А)=1 для всех вариантов. Вариант ответа Интервал A Значения x для проверки (границы интервала) ((x ∈ А) → (x ∈ [2, 10]) ) \/ (x ∈ [6, 14]) 1 [0, 3] 0, 3 (1→0)V0=0 (1→1)V0=1 2 [3, 11] 3, 11 1 (1→0)V1=1 3 [11, 15] 11, 15 1 (1→0)V0=0 4 [15, 17] 15, 17 0 (1→0)V0=0

Задание А10. Задача: Для какого имени истинно высказывание: ¬ (Первая буква имени гласная → Четвертая буква имени согласная)? 1) ЕЛЕНА 2) ВАДИМ 3) АНТОН 4) ФЕДОР

Решение (рассуждения): Запишем выражение: ¬ (1Г → 4С) 1 перед выражением стоит отрицание, при котором высказывание истинно, значит без отрицания выражение в скобках должно быть ложно: 1Г → 4С  0 импликация ложна, если ее первая часть («посылка») истинна, а вторая («следствие») – ложна: 1Г  1 4С  0 первое условие истинно, когда первая буква гласная, то есть для ответов 1 и 3 второе условие «четвертая буква согласная» ложно тогда, когда четвертая буква гласная, то есть, для ответа 3: 4Г  1 таким образом, для варианта 3 исходное условие в целом истинно ответ: 1.

Читайте также:  Ресурсообеспеченность стран мира рудами таблица

Разбор задачи B12 В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет. Какое количество страниц (в тысячах) будет найдено по запросу Эсминец? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов. Запрос Найдено страниц (в тысячах) Фрегат | Эсминец 3400 Фрегат & Эсминец 900 Фрегат 2100

Решение: Изобразим запросы в виде диаграмм Эйлера-Венна. Запрос «Фрегат» обозначим символом «Ф», «Эсминец» — символом «Э». Э=(Ф|Э)-Ф+(Ф&Э)=3400-2100+900=2200.

I. Простая задача, решаемая с методом рассуждений: Сколько различных решений имеет уравнение (K  L  M)  (¬L  ¬M  N) = 1 N-любое (0 или 1) K-любое, L=0, M=0, N=1, всего два решения Примеры решения задач Итого 7 х 2 = 14 решений Есть только одно совпадающее решение K=1, L=0, M=0, N=1 Сколько будет решений, если заменить  →  ? K L M N 0 0 1 0(1) 0 1 0 0(1) 0 1 1 0(1) 1 0 0 0(1) 1 0 1 0(1) 1 1 0 0(1) 1 1 1 0(1) K L M N 0 0 0 1 1 0 0 1

Задание В 15. Задача. Сколько различных решений имеет уравнение (M N)  ((N  K)  (¬L M))0, где K,L,M,N — логические переменные. Решение (вариант 2, составление таблицы истинности): нужно для каждой строчки подставить значения K,L,M,N и вычислить значение функции для четырех комбинаций K,L,M,N результат будет ложным. Ответ: 4. K L M N M N N  K ¬L ¬L M (N K)  (¬L M) (M N)  ((N  K)  (¬L M))0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 0 0 0 0 1 1 0 1 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1

II. Задача, решаемая с методом рассуждений: Сколько различных решений имеет уравнение (X1  X2)(X2  X3)(X3  X4)(X4  X5) = 1 Все скобки должны быть равны 1 Операция импликации дает только одно решение = 0, когда 1  0, то есть нельзя, чтобы после 1 был 0 Примеры решения задач Вывод: Количество решений на единицу больше количества переменных (6 реш.) Если X1…X10, то количество решений будет равно 11 Х1 Х2 Х3 Х4 Х5 1 0 0 0 0 0 2 0 0 0 0 1 3 0 0 0 1 1 4 0 0 1 1 1 5 0 1 1 1 1 6 1 1 1 1 1

III. Задача, решаемая с помощью замены переменных: Сколько различных решений имеет система уравнений ((x1 ≡ x2)  (x3 ≡ x4))  (¬(x1 ≡ x2)  ¬(x3 ≡ x4)) =1 ((x3 ≡ x4)  (x5 ≡ x6))  (¬(x3 ≡ x4)  ¬(x5 ≡ x6)) =1 ((x5 ≡ x6)  (x7 ≡ x8))  (¬(x5 ≡ x6)  ¬(x7 ≡ x8)) =1 ((x7 ≡ x8)  (x9 ≡ x10))  (¬(x7 ≡ x8)  ¬(x9 ≡ x10)) =1 Примеры решения задач t1 = (x1 ≡ x2) t2 = (x3 ≡ x4) t3 = (x5 ≡ x6) t4 = (x7 ≡ x8) t5 = (x9 ≡ x10) Произведем замену: Перепишем уравнения, заметим, что уравнения = 1, когда t1 ≠ t2 ( t1  t2 )  ( ¬ t1  ¬ t2) =1 ( t2  t3 )  ( ¬ t2  ¬ t3) =1 ( t3  t4 )  ( ¬ t3  ¬ t4) =1 ( t4  t5 )  ( ¬ t4  ¬ t5) =1

Поскольку значения переменных в скобках должны быть разными, они будут чередоваться: Примеры решения задач t1 = (x1 ≡ x2) t2 = (x3 ≡ x4) t3 = (x5 ≡ x6) t4 = (x7 ≡ x8) t5 = (x9 ≡ x10) Для каждой комбинации из 5-ти значений t1 … t5 существует по 2 решения: если t1 = 0, то x1 =1, x2 =0 или x1 =0, x2 =1 если t1 = 1, то x1 =1, x2 =1 или x1 =0, x2 =0 ( t1  t2 )  ( ¬ t1  ¬ t2) =1 ( t2  t3 )  ( ¬ t2  ¬ t3) =1 ( t3  t4 )  ( ¬ t3  ¬ t4) =1 ( t4  t5 )  ( ¬ t4  ¬ t5) =1 Получим 2 решения: То есть 2 варианта по 5 переменным дают 25=32 решения, 32+32=64 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1

Источники дополнительных сведений ФИПИ http://www.fipi.ru/view Открытый сегмент ЕГЭ http://www.fipi.ru/view/sections/160/docs/ КИМ ЕГЭ по информатике http://www.fipi.ru/view/sections/226/docs/627.html Сайт на Яндексе www.ege.yandex.ru

  • Все материалы
  • Статьи
  • Научные работы
  • Видеоуроки
  • Презентации
  • Конспекты
  • Тесты
  • Рабочие программы
  • Другие методич. материалы

Номер материала: 43003032828

Не нашли то что искали?

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

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

Время чтения: 18 минут

Цены на канцелярские товары перед школьным сезоном вырастут на 10–30%

Время чтения: 1 минута

Специалисты ВШЭ предложили по-новому рассчитывать зарплату учителям

Время чтения: 2 минуты

Минпросвещения намерено ограничить продвижение готовых домашних заданий

Время чтения: 2 минуты

В Калининграде работникам образования выплатят по 10 тыс. рублей

Время чтения: 1 минута

В школах Подмосковья отменили бумажные медсправки

Время чтения: 1 минута

Подарочные сертификаты

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

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.

Источник

Дан фрагмент таблицы истинности выражения F:

Дан фрагмент таблицы истинности выражения F:

Сколько строк таблицы удовлетворяют выражению: F = (x1 ∨ x2 ∨ x3) ∧ x4 ∧ (x5 ∨ x6 ∨ x7) ∧ x8?

Данное выражение является конъюнкцией четырёх выражений. Конъюнкция нескольких высказываний истинна тогда и только тогда, когда истинными являются все входящие в неё высказывания. Следовательно, x4 = 1, x8 = 1 и в наборах значений переменных (x1, x2, x3), (x5, x6, x7) должна быть хотя бы одна 1.

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

Чтобы остальные строки удовлетворяли заданному выражению, значение F должно быть равно 0. В таблице количество таких строк равно 5.

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

Источник

Задача №2. Построение таблиц истинности логических выражений. Выбор выражения, соответствующего условию.

В компьютере вся информация представлена в двоичной системе счисления, в которой используется две цифры – 0 и 1. Собственно, и цифр как таковых у компьютера нет, а есть электрический сигнал, проходящий по электронным схемам и соединительным проводникам (шинам) компьютера, который может принимать значения “высокий уровень электрического напряжения” (принимаемый нами за 1) и “низкий уровень электрического напряжения” (принимаемый за 0). Для различных действий над этими нулями и единичками нам необходимы специальные операции, которые работают с двоичными переменными. Такие операции называются логическими операциями.

Логические операции и их аргументы принимают только два значения: 1 (“истина”) и 0 (“ложь”).

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

Количество строк в таблице истинности выражения от N переменных равно 2 N .

Основные логические операции:

1). Логическое умножение (конъюнкция, логическое И). Обозначается: AND, &, /\.

A

B

А&В

2). Логическое сложение (дизъюнкция, логическое ИЛИ). Обозначается: OR, |, \/.

A

B

A \/ B

3). Логическое отрицание (инверсия, логическое НЕ). Обозначается: NOT, ¬, .

A

¬ А

4). Логическое следование (импликация). Обозначается: .

A

B

A B

5). Логическое равенство (эквивалентность). Обозначается: ↔,

A

B

A

B

Порядок (приоритет) выполнения логических операций:

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

— Логическое отрицание (инверсия, логическое НЕ);

— Логическое умножение (конъюнкция, логическое И);

— Логическое сложение (дизъюнкция, логическое ИЛИ);

— Логическое следование (импликация);

— Логическое равенство (эквивалентность).

Выбор выражения по таблице истинности

Дан фраг­мент таб­ли­цы ис­тин­но­сти вы­ра­же­ния F:

x1

x2

x3

x4

x5

x6

F

Каким вы­ра­же­ни­ем может быть F?

1) (x1 ∧ x2) ∨ (x3 ∧ x4) ∨ (x5 ∧ x6)

2) (x1 ∧ x3) ∨ (x3 ∧ x5) ∨ (x5 ∧ x1)

3) (x2 ∧ x4) ∨ (x4 ∧ x6) ∨ (x6 ∧ x2)

4) (x1 ∧ x4) ∨ (x2 ∧ x5) ∨ (x3 ∧ x6)

Все пред­став­лен­ные ва­ри­ан­ты от­ве­та — дизъ­юнк­ции трёх конъ­юнк­ций. Все зна­че­ния F в таблице равны нулю. Дизъ­юнк­ция равна нулю, когда все слагаемые равны нулю.

Рас­смот­ри по­очерёдно все че­ты­ре вы­ра­же­ния.

1) В пер­вой стро­ке таб­ли­цы x1=1 и x2=1, зна­чит x1∧x2=1. Выражение не подходит.

2) Во вто­рой стро­ке таб­ли­цы x1=1 и x3=1, зна­чит x1∧x3=1. Выражение не подходит.

3) Подставим в третье выражение поочередно значения всех строк таблицы:

(x2 ∧ x4) ∨ (x4 ∧ x6) ∨ (x6 ∧ x2) = (1 ∧ 0) ∨ (0 ∧ 0) ∨ (0 ∧ 1) = 0 ∨ 0 ∨ 0 = 0

(x2 ∧ x4) ∨ (x4 ∧ x6) ∨ (x6 ∧ x2) = (0 ∧ 0) ∨ (0 ∧ 1) ∨ (1 ∧ 0) = 0 ∨ 0 ∨ 0 = 0

(x2 ∧ x4) ∨ (x4 ∧ x6) ∨ (x6 ∧ x2) = (0 ∧ 1) ∨ (1 ∧ 0) ∨ (0 ∧ 0) = 0 ∨ 0 ∨ 0 = 0

4) В тре­тьей стро­ке таб­ли­цы x1=1 и x4=1, зна­чит x1∧x4=1. Выражение не подходит.

Для таб­ли­цы ис­тин­но­сти функ­ции F из­вест­ны зна­че­ния толь­ко не­ко­то­рых ячеек:

x1

x2

x3

x4

x5

x6

x7

F

Каким вы­ра­же­ни­ем может быть F?

1) x1 ∧ x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7

2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ ¬x7

3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ x6 ∧ x7

4) x1 ∨ x2 ∨ ¬ x3 ∨ x4 ∨ x5 ∨ ¬x6 ∨ x7

Рас­смот­ри по­очерёдно все че­ты­ре вы­ра­же­ния.

1) Выражение является конъюнкцией переменных и их отрицаний. Конъюнкция равна единице, когда все операнды равны единице. В первой строке x6 = 0, а значит и все выражение F равно нулю, что не со­от­вет­ству­ет таб­ли­це ис­тин­но­сти.

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

x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 = x1 ∨ ¬x2 ∨ x3 ∨ 0 ∨ ¬x5 ∨ 0 ∨ ¬x7 может принимать значение 1, если хотя бы один из операндов равен 1.

x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 = x1 ∨ ¬x2 ∨ x3 ∨ 1 ∨ ¬x5 ∨ x6 ∨ 1 = 1

x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 = 0 ∨ ¬x2 ∨ x3 ∨ 0 ∨ ¬x5 ∨ x6 ∨ ¬x7 может принимать значение 0, если все остальные операнды равны 0.

3) Выражение является конъюнкцией переменных и их отрицаний. Конъюнкция равна единице, когда все операнды равны единице. Во второй строке x4 = 0, а значит и все выражение F равно нулю, что не со­от­вет­ству­ет таб­ли­це ис­тин­но­сти.

4) Выражение является дизъюнкцией переменных и их отрицаний. Дизъюнкция равна единице, когда хотя бы один операнд равен единице. В третьей строке x4 = 1, значит и все выражение F равно 1, что не со­от­вет­ству­ет таб­ли­це ис­тин­но­сти.

Логическая функция F задаётся выражением (¬z) ∧ x ∨ x ∧ y. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.

Источник

Adblock
detector