Решу егэ алгебра логики информатика - Помощь в подготовке к экзаменам и поступлению

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

Перем. 1	Перем. 2	Перем. 3	Функция
???	???	???	F
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	0

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

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

Перем. 1	Перем. 2	Функция
???	???	F
0	0	1
0	1	0
1	0	1
1	1	1

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

Источник

Всего: 191 1–20 | 21–40 | 41–60 | 61–80 …

Добавить в вариант

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Так, например, 14&5  =  1110₂&0101₂  =  0100₂  =  4.

Для какого наибольшего целого числа А формула

x&51 = 0 ∨ (x&41 = 0 → x&А = 0)

тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Так, например, 14&5  =  1110₂&0101₂  =  0100₂  =  4.

Для какого наименьшего неотрицательного целого числа А формула

x&51 = 0 ∨ (x&41 = 0 → x&А = 0)

тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной x)?

На числовой прямой даны два отрезка: P = [17, 46] и Q = [22, 57]. Отрезок A таков, что приведённая ниже формула истинна при любом значении переменной х:

¬(x ∈ A) →(((x ∈ P) ⋀ (x ∈ Q)) → (x ∈ A))

Какова наименьшая возможная длина отрезка A?

На числовой прямой даны два отрезка: Р = [30, 45] и Q = [40, 55]. Какова наименьшая возможная длина интервала A, что обе приведённые ниже формулы истинны при любом значении переменной х:

( ¬(x ∈ A) → (¬(x ∈ P)) )

((x ∈ Q)→ (x ∈ A))

На числовой прямой даны два отрезка: Р = [3, 38] и Q = [21, 57]. Какова наибольшая возможная длина интервала A, что логическое выражение

((х ∈ Q) → (х ∈ Р)) → ¬(х ∈ A)

тождественно истинно, то есть принимает значение 1 при любом значении переменной х.

На числовой прямой даны два отрезка: P = [1, 39] и Q = [23, 58]. Какова наибольшая возможная длина интервала A, что логическое выражение

((x ∈ P) → ¬(x ∈ Q)) → ¬(x ∈ А)

тождественно истинно, то есть принимает значение 1 при любом значении переменной х.

На числовой прямой даны два отрезка: D  =  [17; 58] и C  =  [29; 80]. Укажите наименьшую возможную длину такого отрезка A, для которого логическое выражение

(x ∈ D) → ((¬(x ∈ C)∧ ¬(x ∈ A)) → ¬(x ∈ D))

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

Источник: Демонстрационная версия ЕГЭ−2022 по информатике

На числовой прямой даны два отрезка: P = [4, 15] и Q = [12, 20].

Укажите наименьшую возможную длину отрезка A, для которого выражение

((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A)

тождественно истинно, то есть принимает значение 1 при любом значении переменной х.

На числовой прямой даны два отрезка: P = [20, 50] и Q = [30,65]. Отрезок A таков, что формул

¬(x ∈ A) → ((x ∈ P) →¬ (x ∈ Q))

истинна при любом значении переменной x. Какова наименьшая возможная длина отрезка A?

Источник: ЕГЭ по информатике 23.03.2016. Досрочная волна

На числовой прямой задан отрезок A. Известно, что формула

((x ∈ A) → (x² ≤ 100)) ∧ ((x² ≤ 64) → (x ∈ A))

тождественно истинна при любом вещественном x. Какую наименьшую длину может иметь отрезок A?

На числовой прямой даны два отрезка: P = [2, 10] и Q = [6, 14]. Какова наибольшая возможная длина интервала A, что формула

( (x ∈ А) → (x ∈ P) ) ∨ (x ∈ Q)

тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

На числовой прямой даны три отрезка: P = [10, 40], Q = [5, 15] и R = [35, 50]. Какова наименьшая возможная длина промежутка A, что формула

( (x ∈ А) ∨ (x ∈ P) ) ∨ ((x ∈ Q)→ (x ∈ R))

тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

На числовой прямой даны два отрезка: P = [12, 62] и Q = [32, 92].

Какова наименьшая возможная длина интервала A, что формула

(¬(x ∈ А) ∧ (x ∈ Q)) → (x ∈ P)

тождественно истинна, т. е. принимает значение 1 при любом значении переменной х.

На числовой прямой даны два отрезка: P = [8, 39] и Q = [23, 58].

Какова наименьшая возможная длина интервала A, при которой выражение

((x ∈ P) ∨ (x ∈ А)) → ((x ∈ Q) ∨ (x ∈ А))

тождественно истинно, то есть принимает значение 1 при любом значении переменной х.

На числовой прямой даны два отрезка: P  =  [17, 54] и Q  =  [37, 83]. Какова наименьшая возможная длина интервала A, что формула

(x ∈ P) → (((x ∈ Q) ∧ ¬(x ∈ A)) → ¬(x ∈ P))

тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

Источник: ЕГЭ по информатике 2021. Досрочная волна

Элементами множества А являются натуральные числа. Известно, что выражение

(x ∈ {2, 4, 6, 8, 10, 12}) → (((x ∈ {3, 6, 9, 12, 15}) ∧ ¬(x ∈ A)) → ¬(x ∈ {2, 4, 6, 8, 10, 12}))

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.

Элементами множества А являются натуральные числа. Известно, что выражение

(x ∈ {2, 4, 6, 8, 10, 12}) → (((x ∈ {4, 8, 12, 16}) ∧ ¬(x ∈ A)) → ¬(x ∈ {2, 4, 6, 8, 10, 12}))

На числовой прямой даны два отрезка: Р = [22, 72] и Q = [42, 102]. Какова наименьшая возможная длина интервала A, что логическое выражение

¬(¬(х ∈ А) ∧ (х ∈ Р)) ∨ (х ∈ Q)

тождественно истинно, то есть принимает значение 1 при любом значении переменной х.

На числовой прямой даны два отрезка: Р = [12, 62] и Q = [52, 92]. Какова наименьшая возможная длина интервала A, что логическое выражение

¬(¬(х ∈ А) ∧ (х ∈ Р)) ∨ (х ∈ Q)

тождественно истинно, то есть принимает значение 1 при любом значении переменной х.

На числовой прямой даны два отрезка: P = [3, 13] и Q = [12, 22]. Какова наибольшая возможная длина интервала A, что формула

((х ∈ A) → (х ∈ Р)) ∨ (х ∈ Q)

тождественно истинна, то есть принимает значение 1 при любом значении переменной х.

Всего: 191 1–20 | 21–40 | 41–60 | 61–80 …

Источник

На уроке рассматривается разбор 2 задания ЕГЭ по информатике, дается подробное объяснение того, как решать подобные задачи

Содержание:

Объяснение задания 2 ЕГЭ по информатике
- Таблицы истинности и порядок выполнения логических операций
Решение заданий 2 ЕГЭ по информатике
- Задания для тренировки

2-е задание: «Таблицы истинности»

Уровень сложности

— базовый,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 3 минуты.

Проверяемые элементы содержания: Умение строить таблицы истинности и логические схемы

Типичные ошибки и рекомендации по их предотвращению:

«Игнорирование прямо указанного в условии задания требования, что заполненная таблица истинности не должна содержать одинаковых строк. Это приводит к внешне правдоподобному, но на самом деле неверному решению»

ФГБНУ «Федеральный институт педагогических измерений»

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

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

операция	пояснение	в программировании
¬ A, A	не A (отрицание, инверсия)	not(A)
A ∧ B, A ⋅ B	A и B (логическое умножение, конъюнкция)	A and B
A ∨ B, A + B	A или B (логическое сложение, дизъюнкция)	A or B
A → B	импликация (следование)	A <= B
A ↔ B, A ≡ B, A ∼ B	эквиваленция (эквивалентность, равносильность)	A==B (python) A=B(pascal)
A ⊕ B	строгая дизъюнкция	A != B (python) A <> B (pascal)

Егифка ©:

Отрицание (НЕ):

Таблица истинности операции НЕ

Конъюнкция (И):

Таблица истинности операции И (конъюнкция)

Дизъюнкция (ИЛИ):

Таблица истинности операции ИЛИ (дизъюнкция)

Импликация (если…, то…):

Таблица истинности операции Импликация (если…, то…)

Эквивалентность (тогда и только тогда, …):

Таблица истинности операции Эквивалентность (тогда и только тогда, …)

Сложение по модулю 2 (XOR):

A	B	A ⊕ B
0	0	0
0	1	1
1	0	1
1	1	0

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

если нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», импликация, равносильность

Еще о логических операциях:

логическое произведение X∙Y∙Z∙… равно 1, т.е. выражение является истинным, только тогда, когда все сомножители равны 1 (а в остальных случаях равно 0)
логическая сумма X+Y+Z+… равна 0, т.е. выражение является ложным только тогда, когда все слагаемые равны 0 (а в остальных случаях равна 1)

О преобразованиях логических операций читайте здесь.

Егифка ©:

Решение заданий 2 ЕГЭ по информатике

Задание 2_11: Решение 2 задания ЕГЭ по информатике:

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

(¬x ∨ y ∨ z) ∧ (x ∨ ¬z ∨ ¬w)

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

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

Перем.1	Перем.2	Перем.3	Перем.4	F
???	???	???	???	F
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	1	0	0	0

В ответе запишите буквы в том порядке, в котором идут соответствующие им столбцы.

✍ Решение:

✎ Способ 1. Электронные таблицы Excel + Логические размышления:

Отобразим перебор всех значений использующихся в выражении переменных (всю таблицу истинности). Поскольку в выражении используются 4 переменных, то строк таблицы будет 2⁴=16:

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

Выделите таблицу и отсортируйте строки по столбцу с результатом функции. Для этого в меню Главная => Настраиваемая сортировка =>:

Получили верхние строки таблицы — с которыми сравним исходную таблицу и найдем результат:

Получаем следующий порядок переменных:

xwzy

✎ Способ 2. Программирование:

Язык python:

print('x y z w')
for x in 0, 1:
  for y in 0, 1:
    for z in 0, 1:
      for w in 0, 1:
        F = (not(x) or y or z) and (x or not(z) or not(w))
        if not(F):
          print(x, y, z, w)

В результате будут выведены значения для F=0:

Сопоставив их с исходной таблицей, получим результат:

xwzy

Язык pascalAbc.net:

begin
  writeln('x':7, 'y':7, 'z':7,'w':7);
  for var x:=false to true do
    for var y:=false to true do
      for var z:=false to true do
        for var w:=false to true do
          if not((not x or y or z) and (x or not z or not w)) then
            writeln(x:7, y:7, z:7,w:7);
end.

В результате будут выведены значения для F=0:

      x      y      z      w
  False  False   True   True
  False   True   True   True
   True  False  False  False
   True  False  False   True

Где false = 0, True = 1
Сопоставив их с исходной таблицей, получим результат:

Ответ:

xwzy

✎ Способ 3. Логические размышления:

Внешняя операция выражения — конъюнкция (∧). Во всех указанных строках таблицы истинности функция принимает значение 0 (ложь). Конъюнкция ложна аж в трех случаях, поэтому проверить на ложь очень затруднительно. Тогда как конъюнкция истинна (= 1) только в одном случае: когда все операнды истинны. Т.е. в нашем случае:

(¬x ∨ y ∨ z) ∧ (x ∨ ¬z ∨ ¬w) = 1 когда:
1. (¬x ∨ y ∨ z) = 1 
И 
2. (x ∨ ¬z ∨ ¬w) = 1

Общая идея дальнейшего решения такова: поскольку внешняя операция — конъюнкция, и результат ее истинен, когда оба сомножителя в скобках будут истинны (=1), то нам необходимо сначала составить все наборы таблицы истинности для обоих сомножителей в скобках. Затем, так как конъюнкция подразумевает пересечение, необходимо сопоставить обе таблицы истинности и выбрать для каждого подходящего набора первого сомножителя подходящий (подходящие) набор (наборы) второго сомножителя. НО! так как у нас в задании известны только наборы для F = 0, то мы сопоставлять будем наборы, которые возвращают ложь. Теперь подробно.
Разобьём исходное выражение на две части и составим таблицу истинности отдельно для двух частей.
Для сомножителя (¬x ∨ y ∨ z):

x	y	z	результат
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Получили ложь в одном наборе, так как дизъюнкция (∨) ложна только тогда, когда ложны все операнды.
Для сомножителя (x ∨ ¬z ∨ ¬w):

x	z	w	результат
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Соответственно, опять получили ложь в одном наборе, когда ложны все операнды.
Учтем, что нам нужно выбрать и «пересечь» (так как внешняя операция ∧) из всех наборов только те, которые возвращают ложь (так как по заданию известны только строки, где F = 0):

Выпишем только пересеченные наборы:

x	y	z	w	F
0	0	1	1	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0

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

x	y	z	w	F
0	0	1	1	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0

x	???	???	???	F
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	1	0	0	0

Сравнив первую и четвертую одинаковые строки получившейся таблицы, находим, что y в обоих случаях равен 0. Значит он находится в 4-м столбце.

x	y	z	w	F
0	0	1	1	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0

x	???	???	y	F
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	1	0	0	0

Сравнив предпоследнюю и последнюю строки получившейся таблицы, там где x = 1, находим, что z в обоих случаях равен 0, тогда как w принимает значение и 1 и 0. Значит z находится в 3-м столбце.

x	y	z	w	F
0	0	1	1	0
0	1	1	1	0
1	0	0	0	0
1	0	0	1	0

Для w остается второй столбец:

x	w	z	y	F
0	1	1	0	0
0	1	1	1	0
1	0	0	0	0
1	1	0	0	0

Результат: xwzy

🎦 Видеорешение (бескомпьютерный вариант):

📹 здесь
📹 Видеорешение на RuTube здесь

Задание 2_12: Разбор 2 задания ЕГЭ:

Миша заполнял таблицу истинности функции:

(¬z ∧ ¬(x ≡ y)) → ¬(y ∨ w)

но успел заполнить лишь фрагмент из трех различных ее строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z:

Перем.1	Перем.2	Перем.3	Перем.4	F
???	???	???	???	F
1	1			0
1		0		0
	1	1	0	0

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

В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы.

Подобные задания для тренировки

✍ Решение:

✎ Способ 1. Логические размышления (бескомпьютерный вариант):

Решим задание методом построения полной таблицы истинности.
Посчитаем общее количество строк в таблице истинности и построим ее:

4 переменных -> 2⁴ = 16 строк

Для начала упростим выражение и выделим в нем две основные части относительно внешней операции (операция, которая выполняется последней).

(¬z ∧ ¬(x ≡ y)) → ¬(y ∨ w)
1. Избавимся от импликации:
¬(¬z ∧ ¬(x ≡ y)) ∨ ¬(y ∨ w)
2. Внесем знак отрицания в скобки (закон Де Моргана):
(z ∨ (x ≡ y)) ∨ (¬y ∧ ¬w) = 0
   ^{1 часть = 0     2 часть = 0}

* Исходное выражение должно быть = 0. Дизъюнкция = 0, когда оба операнда равны 0.

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

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

(z ∨ (x ≡ y)) = 0 когда z = 0 и x ≡ y = 0

¬y ∧ ¬w = 0 когда:
1. ¬y = 0  ¬w = 0
2. ¬y = 1  ¬w = 0
3. ¬y = 0  ¬w = 1

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

x	y	w	z	F
0	1	0	0	0
0	1	1	0	0
1	0	1	0	0

Сравнив их с исходной таблицей истинности, имеем:

y	w	x	z	F
1	1	0	0	0
1	0	0	0	0
0	1	1	0	0

Таким образом, ответ: ywxz

Результат: ywxz

✎ Способ 2. Программирование:

Язык PascalAbc.net:

begin
  writeln('x':7, 'y':7, 'z':7,'w':7);
  for var x:=false to true do
    for var y:=false to true do
      for var z:=false to true do
        for var w:=false to true do
          if not((not z and (x xor y)) <= not(y or w)) then
            writeln(x:7, y:7, z:7,w:7);
end.

В результате будут выведены значения для F=0:

      x      y      z      w
  False   True  False  False
  False   True  False   True
   True  False  False   True

Где false = 0, True = 1

Сопоставив их с исходной таблицей, получим результат: ywxz

Язык Python:

print ('x y z w')
for x in 0,1:
    for y in 0,1:
        for z in 0,1:
            for w in 0,1:
                F=(not z and not(x==y))<=(not(y or w))
                if not F:
                    print (x,y,z,w)

В результате будут выведены значения для F=0:

Сопоставив их с исходной таблицей, получим результат:

Результат: ywxz

🎦 Доступно видео решения этого задания (бескомпьютерный вариант):

📹 здесь
📹 Видеорешение на RuTube здесь

🎦 Видео (решение 2 ЕГЭ в Excel):

📹 здесь
📹 Видеорешение на RuTube здесь
📹 Видеорешение на RuTube здесь (Программирование)

Задание 2_10: Решение 2 задания ЕГЭ по информатике:

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

¬a ∧ b ∧ (c ∨ ¬d)

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

Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных a, b, c, d.

Перем.1	Перем.2	Перем.3	Перем.4	F
???	???	???	???	F
0	1	0	0	1
1	1	0	0	1
1	1	0	1	1

В ответе запишите буквы в том порядке, в котором идут соответствующие им столбцы.

✍ Решение:

🎦 (Бескомьютерный вариант) Предлагаем подробный разбор посмотреть на видео:

📹 здесь
📹 Видеорешение на RuTube здесь

Задание 2_3: Решение задания 2. Демоверсия ЕГЭ 2018 информатика:

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

Перем. 1	Перем. 2	Перем. 3	Перем. 4	F
???	???	???	???	F
1	0	0	0	0
1	1	0	0	0
1	1	1	0	0

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

Подобные задания для тренировки

✍ Решение:

✎ Логические размышления (бескомпьютерный вариант):

Внешним действием (последним выполняемым) в исходном выражении является дизъюнкция:

¬x ∨ y ∨ (¬z ∧ w)

Вспомним таб. ист-ти для дизъюнкции (логическое сложение):

x1	x2	F
0	0	0
0	1	1
1	0	1
1	1	1

Чтобы исходное выражение было истинным, нужно, чтобы хотя бы один из операндов равнялся единице. Т.е. нельзя наверняка сказать, где будет 1, а где 0 (¬x = 1 или 0, y = 1 или 0, ¬z ∧ w = 1 или 0).
Функция же ложна только в одном случае, — когда все операнды ложны. Поэтому будем искать по признаку лжи.
В исходной таблице истинности во всех строках функция ложна. Чтобы понять в каком столбце должна находиться та или иная переменная, возьмем за основу строку, в которой только одна единица или только один нуль.
Строка №1: в ней одна единица — первый столбец. В исходной формуле, чтобы функция была ложна, необходимо, чтобы ¬x = 0, иными словами x = 1. Значит первый столбец соответствует переменной x.

Перем. 1	Перем. 2	Перем. 3	Перем. 4	F
x	???	???	???	F
1	0	0	0	0

Строка №3: в ней один нуль — четвертый столбец. В исходной формуле, чтобы функция была ложна, необходимо, чтобы y = 0. Значит четвертый столбец соответствует переменной y.

Перем. 1	Перем. 2	Перем. 3	Перем. 4	F
x	???	???	y	F
1	1	1	0	0

Строка №2: в ней второй столбец равен единице, а третий — нулю. В исходном выражении ¬z ∧ w должно равняться 0, чтобы функция была ложной. Конъюнкция истинна только тогда, когда оба операнда истинны (=1); в нашем случае функция должна быть ложной, но пойдем от обратного. Если ¬z = 1, т.е. z = 0, а w = 1, то это неверно для нашего случая. Значит всё должно быть наоборот: z = 1, а w = 0. Таким образом столбец второй соответствует z, а столбец третий — w.

x	z	w	y	F
1	0	0	0	0
1	1	0	0	0
1	1	1	0	0

Результат: xzwy

✎ Способ 2. Программирование:
Язык pascalABC.NET:

begin
  writeln('x  ','y  ','z  ','w  ');
  for var x:=false to true do
    for var y:=false to true do
      for var z:=false to true do
        for var w:=false to true do
          if not(not x or y or(not z and w)) then
            writeln(x:7,y:7,z:7,w:7);
end.

🎦 (бескомпьютерный вариант) Подробное решение данного 2 задания из демоверсии ЕГЭ 2018 года смотрите на видео:

📹 здесь
📹 Видеорешение на RuTube здесь

Задание 2_13: Разбор досрочного егэ по информатике 2019

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

(x ∧ ¬y) ∨ (y ≡ z) ∨ ¬w

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

Перем.1	Перем.2	Перем.3	Перем.4	F
???	???	???	???	F
0			0	0
0	1	0	1	0
	1	0		0

✍ Решение:

🎦 Видеорешение (бескомпьютерный вариант):
📹 здесь
📹 Видеорешение на RuTube здесь

Задания для тренировки

Задание 2_2: Задание 2 ЕГЭ по информатике:

Каждое из логических выражений F и G содержит 5 переменных. В табл. истинности для F и G есть ровно 5 одинаковых строк, причем ровно в 4 из них в столбце значений стоит 1.

Сколько строк таблицы истинности для F ∨ G содержит 1 в столбце значений?

Подобные задания для тренировки

✍ Решение:

Поскольку в каждом из выражений присутствует 5 переменных, то эти 5 переменных порождают таблицу истинности из 32 строк: т.к. каждая из переменных может принимать оно из двух значений (0 или 1), то различных вариантов с пятью переменными будет 2⁵=32, т.е. 32 строки.
Из этих 32 строк и для F и для G мы знаем наверняка только о 5 строках: 4 из них истинны (=1), а одна ложна (=0).
Вопрос стоит о количестве строк = 1 для таб. истинности F ∨ G. Данная операция — дизъюнкция, которая ложна только в одном случае — если F = 0 и одновременно G = 0
В исходных таблицах для F и G мы знаем о существовании только одного 0, т.е. в остальных строках может быть 1. Т.о., и для F и для G в 31 строке могут быть единицы (32-1=31), а лишь в одной — ноль.
Тогда для F ∨ G только в одном случае будет 0, когда и F = 0 и G = 0:

№	F	G	F ∨ G
1	0	0	0
2	0	1	1
…	…	…	1
32	…	…	1

Соответственно, истинными будут все остальные строки:

32 - 1 = 31

Результат: 31

Подробное объяснение данного задания смотрите на видео:

📹 здесь

Задание 2_6: Решение 2 задания ЕГЭ по информатике:

Каждое логическое выражение A и B зависит от одного и того же набора из 7 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 4 единицы.

Каково максимально возможное число единиц в столбце значений таблицы истинности выражения A ∨ B?

✍ Решение:

Полная таблица истинности для каждого из выражений A и B состоит из 2⁷ = 128 строк.
В четырех из них результат равен единице, значит в остальных — 0.
A ∨ B истинно в том случае, когда либо A = 1 либо B = 1, или и A и B = 1.
Поскольку А = 1 только в 4 случаях, то чтобы получить максимальное количество единиц в результирующей таблице истинности (для A ∨ B), расположим все единицы т.и. для выражения A так, чтобы они были в строках, где B = 0, и наоборот, все строки, где B = 1, поставим в строки, где A = 0:

A	B
1	0
1	0
1	0
1	0
0	1
0	1
0	1
0	1
0	0
…	…

Итого получаем 8 строк.
Если бы в задании требовалось найти минимальное количество единиц, то мы бы совместили строки со значением = 1, и получили бы значение 4.

Результат: 8

Задание 2_7: Решение 2 задания ЕГЭ по информатике:

Каждое логическое выражение A и B зависит от одного и того же набора из 8 переменных. В таблицах истинности каждого из этих выражений в столбце значений стоит ровно по 6 единиц.

Каково максимально возможное число нулей в столбце значений таблицы истинности выражения A ∧ B?

✍ Решение:

Полная таблица истинности для каждого из выражений A и B состоит из 2⁸ = 256 строк.
В шести из них результат равен единице, значит в остальных — 0.

A ∧ B ложно в том случае, когда:

A ∧ B = 0 если:

1. A = 0, B = 1 
2. B = 0, A = 1
3. A = 0 и B = 0

Во всех случаях там где А=1 может стоять B=0, и тогда результат F = 0. Поскольку нам необходимо найти максимально возможное число нулей, то как раз для всех шести А=1 сопоставим B=0, и наоборот, для всех шести возможных B=1 сопоставим A=0

A	B	F
1	0	0
1	0	0
1	0	0
1	0	0
0	1	0
0	1	0
0	1	0
0	1	0
0	0	0
…	…	…

Поскольку строк всего 256, то вполне возможно, что все 256 из них возвратят в результате 0

Результат: 256

Задание 2_4: 2 задание:

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

x1	x2	x3	x4	x5	x6	x7	F
1	0	0	1	1	1	1	0
0	1	0	0	1	0	1	1
0	1	0	1	1	0	1	0

Каким из приведённых ниже выражений может быть 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

✍ Решение:

В первом внешняя операция (выполняется последней) — конъюнкция. Начнем рассмотрение с нее. Соответственно, проверяем по второй строке таб. ист-ти, там где F = 1, так как в таком случае все аргументы должны быть истинными (см. таб. истинности для конъюнкции).
Если мы подставим в нее все аргументы выражения, то функция действительно возвращает истину. Т.е. пункт первый подходит:

Но проверим на всякий случай остальные.
Второй пункт проверяем по первой и третьей строке, так как основная операция — дизъюнкция — ложна только в том случае, если все аргументы ложны (см. таб. истинности для дизъюнкции). Проверяя по первой строке, сразу видим, что x1 в ней равен 1. В таком случаем функция будет = 1. Т.е. этот пункт не подходит:

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

Четвертый пункт проверяем по первой и третьей строкам. В первой — x1 = 1, т.е. функция должна быть равна 1. Т.е. пункт тоже не подходит:

Таким образом, ответ равен 1.

Результат: 1

Решение 2 задания ГВЭ по информатике смотрите на видео:

📹 здесь

Задание 2_8: Решение 2 задания ЕГЭ по информатике:

Дано логическое выражение, зависящее от 5 логических переменных:

(¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ x5) ∧ (x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5)

Сколько существует различных наборов значений переменных, при которых выражение истинно?

1) 0
2) 30
3) 31
4) 32

Подобные задания для тренировки

✍ Решение:

Поскольку выражение включает 5 переменных, то таб. ист-ти состоит из 2⁵ = 32 строк.
Внешней операцией (последней) является конъюнкция (логическое умножение), а внутри скобок — дизъюнкция (логическое сложение).
Обозначим первую скобку за А, а вторую скобку за B. Получим A ∧ B.
Найдем сколько нулей существует для таб. истинности:

Теперь рассмотрим каждый случай отдельно:

1 случай. 0 0 : A = 0 и B = 0, то есть:

¬x1 ∨ ¬x2 ∨ ¬x3 ∨ x4 ∨ x5 = 0
и
x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 = 0.

Обратим внимание, что во вторых скобках везде стоит инверсия переменных, которые находятся в первых скобках. Таким образом, это невозможно, так как дизъюнкция равна нулю, когда все операнды равны нулю. А если в первых скобках все 0, то из-за инверсий во вторых скобках все 1. То есть этот случай нам не подходит.
2 случай. 0 1 : нам он подходит, так как если первая скобка возвратит 0, то вторая вернет 1.
3 случай. 1 0 : нам он подходит, так как если вторая скобка возвратит 0, то первая вернет 1.
Итого получаем два случая, когда исходное выражение вернет 0, т.е. две строки таблицы истинности.
Тогда получим количество строк, с результатом равным 1:

32 - 2 = 30, что соответствует номеру 2

Результат: 2

Подробное решение задания смотрите в видеоуроке:

📹 здесь

Задание 2_5: Решение 2 задания ЕГЭ по информатике:

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

x1	x2	x3	x4	x5	x6	F
0	0	1	1	0	0	1
0	0	0	0	1	1	1
1	0	1	0	1	1	1
0	1	1	1	0	1	0

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

Подобные задания для тренировки

✍ Решение:

Полная таблица истинности будет иметь 2⁶ = 64 строк (т.к. 6 переменных).
4 из них нам известны: в них x3 два раза не совпадает с F.
Неизвестных строк:

 
64 - 4 = 60

В неизвестных x3 может не совпадать с F, кроме того, в двух известных x3 не совпадает с F. Соответственно максимально возможное число строк с несовпадающими x3 и F, будет:

60 + 2 = 62

Результат: 62

Задание 2_9: Решение 2 задания ЕГЭ по информатике:

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

x1	x2	x3	x4	x5	x6	x7	F
			0		0		0
			0			0	1
1			1				1

Каким выражением может быть 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 пункт:

(((x1 ∧ (x2 → x3) ∧  ¬x4) ∧ x5) ∧ x6)  ∧ ¬x7

Внешняя операция — конъюнкция. Ее проще проверять по строке, в которой F = 1 (значит все сомножители должны быть равны 1).
Возьмем 3-ю строку, в ней x4=1. В нашем выражении х4 с отрицанием, т.е. = 0. Для конъюнкции, когда хоть один из сомножителей равен нулю, выражение вернет в результате 0, а у нас в строке 1. Т.е. этот пункт не подходит:

2 пункт:

(((x1 ∨ (¬x2 → x3) ∨  ¬x4) ∨ ¬x5) ∨ x6)  ∨ ¬x7

Последняя выполняющаяся операция (внешняя) — дизъюнкция. Ее легче проверять по строке, в которой F = 0 (значит все слагаемые должны быть равны 0).
Смотрим по первой строке: х4 = 0, в рассматриваемом пункте он с отрицанием, т.е. = 1. Соответственно все выражение вернет единицу, а в таблице в строке 0. Т.е. этот пункт не подходит:

3 пункт:

(((¬x1 ∧ (x2 → ¬x3) ∧  x4) ∧ ¬x5) ∧ x6) ∧ x7

Последняя операция — конъюнкция. Ее проще проверять по строке, в которой F = 1 (значит все сомножители должны быть равны 1).
Возьмем 2-ю строку: в ней х7 = 0, в рассматриваем пункте х7 без отрицания, т.е. так и остается равным нулю. При умножении выражение вернет в результате 0. В таблице — 1. Т.е. пункт тоже не подходит:

Единственным подходящим вариантом остался пункт под номером 4 (на всякий случай всегда стоит проверить и его).

Результат: 4

В видеоуроке рассмотрено подробное решение 2 задания:

📹 здесь

Задание 2_1: Задание 2 ЕГЭ по информатике:

Логическая функция F задается выражением
(y → x) ∧ (y → z) ∧ z.

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

№	Перем. 1	Перем. 2	Перем. 3	F
	???	???	???	F
1	0	0	0	0
2	0	0	1	0
3	0	1	0	1
4	0	1	1	1
5	1	0	0	0
6	1	0	1	0
7	1	1	0	0
8	1	1	1	1

В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы.

✍ Решение:

Сначала необходимо рассмотреть логическую операцию, которую мы будем выполнять в последнюю очередь — это логическое И (конъюнкция) или ∧. То есть внешнюю операцию:

(y → x) ∧ (y → z) ∧ z

Конъюнкцию легче рассматривать по тем строкам таб. ист-ти, в которых F = 1, т.е. №3, №4, и №8
Поскольку для конъюнкции функция истинна только тогда, когда все переменные истинны, то необходимо чтобы отдельно каждая скобка была истинна ((y → x) = 1 и (y → z)=1) и переменная z тоже была истинной (=1)

(y → x) ∧ (y → z) ∧ z = 1
   если: 
1. (y → x) = 1
2. (y → z) = 1
3. z = 1

Поскольку с выражениями в скобках сложней работать, определим сначала какому столбцу соответствует z. Для этого выберем строку (№3), где F = 1, а в остальных ячейках только одна единица, остальные — нули.

№	Перем. 1	Перем. 2	Перем. 3	F
3	0	1	0	1

Таким образом, делаем вывод, что z находится во втором столбце (отсчет ведем слева):

№	Перем. 1	Перем. 2	Перем. 3	F
_	???	z	???	F

Дальше нам необходимо рассмотреть две скобки, в которых находится операция импликации: (y → x) и (y → z). Обе эти скобки должны возвращать истину (=1). В таб. истинности для импликации, функция возвращает в результате 1 тогда, когда:
вторая переменная (заключение) равна 1 (первая при этом может быть любой),
вторая переменная (заключение) равна 0, а первая обязательно должна быть равна тоже 0.
Рассмотрим скобку (y → x) и строку 4 таблицы:

№	Перем. 1	z	Перем. 3	F
4	0	1	1	1

Для этой строки только y может быть равен 0, т.к. если x = 0, тогда y=1, и скобка в результате возвратит ложь (1 → 0 = 0). Соответственно, y находится в первом столбце. А x значит должен стоять в третьем:

Результат: yzx

Детальный разбор данного задания 2 ЕГЭ по информатике предлагаем посмотреть в видео:

📹 здесь

Источник

За это задание ты можешь получить 1 балл. На решение дается около 3 минут. Уровень сложности: базовый.
Средний процент выполнения: 65.9%
Ответом к заданию 2 по информатике может быть цифра (число) или слово.

Задача 1

Дано логическое выражение, зависящее от 6 логических переменных:

¬(A → F) ∧ B ∧ ¬C ∧ (D → E).

Сколько существует различных наборов значений переменных, при которых выражение ложно?

Решение

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

¬(A → F) = 1, тогда $A → F = 0$, следовательно, A = 1, F = 0.

B = 1.

¬C = 1, значит C = 0.

(D → E) = 1, тогда возможно 3 варианта: D = 0, E = 0; D = 0, E = 1; D = 1, E = 1.

Перемножим количество подходящих значений для каждой переменной: A, B, C, F — по одному набору, D и E — 3 набора. Итого:

1 х 3 = 3 набора, для которых вся функция истинна. Но нам нужно, чтобы функция была ложна. Найдём общее количество наборов по формуле $k = 2^N$, где N — количество переменных. У нас 6 переменных, значит всего наборов 64. Из них 3 нам не подходят. Тогда количество подходящих (ложных) наборов:

64 — 3 = 61.

Или при помощи программы на С++:

#include <iostream>
#include <algorithm>
#include <fstream>using namespace std;
bool f(int A, int B, int C, int D, int E, int F){
    return (!(!A || F) && B && !C && (!D || E));
}
int main() {
    int count = 0;
    for (int A = 0; A <= 1; ++A)
        for (int B = 0; B <= 1; ++B)
            for (int C = 0; C <= 1; ++C)
                for (int D = 0; D <= 1; ++D)
                    for (int E = 0; E <= 1; ++E)
                        for (int F = 0; F <= 1; ++F)
                            if (f(A, B, C, D, E, F) == false)
                                count++;
    cout << count;
    return 0;
}

Ответ: 61.

Ответ: 61

Задача 2

Дано логическое выражение, зависящее от 5 логических переменных:

$(A ∨ ¬B) ∧ (¬C ∨ D ∨ ¬E)$.

Сколько существует различных наборов значений переменных, при которых выражение ложно?

Решение

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

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

Конъюнкция ложна, когда хотя бы одна скобка ложна. Рассмотрим 3 случая:

Первая скобка ложна, вторая истинна. Первая скобка ложна в 1 случае из 4, вторая истинна в 7 случаях из 8. Итого 7 · 1 = 7.

Первая скобка истинна, вторая ложна. Первая скобка истинна в 3 случаях из 4, вторая ложна в 1 случае из 4. Итого 1 · 3 = 3.

Первая скобка ложна, вторая ложна. Первая скобка ложна в 1 случае из 4, вторая ложна в 1 случае из 8. Итого 1 · 1 = 1.

Суммарно: 7 + 3 + 1 = 11.

Ответ: 11.

Ответ: 11

Задача 3

Дано логическое выражение, зависящее от 5 логических переменных:

(¬A ∧ B ∧ C) ∨ (¬D ∧ ¬E).

Сколько существует различных наборов значений переменных, при которых выражение истинно?

Решение

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

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

Дизъюнкция истинна, когда хотя бы одна скобка истинна. Рассмотрим 3 случая:

Первая скобка ложна, вторая истинна. Первая скобка ложна в 7 случаях из 8, вторая истинна в 1 случае из 4. Итого 7 · 1 = 7.

Первая скобка истинна, вторая ложна. Первая скобка истинна в 1 случае из 8, вторая ложна в 3 случаях из 4. Итого 1 · 3 = 3.

Первая скобка истинна, вторая истинна. Первая скобка истинна в 1 случае из 8, вторая истинна в 1 случае из 4. Итого 1 · 1 = 1.

Суммарно: 7 + 3 + 1 = 11.

Ответ: 11.

Ответ: 11

Задача 4

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

				F
1	0	0	0	1
1	1	0	0	1
1	1	1	0	1

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

Решение

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

bool f(int x, int y, int z, int w){
    return (((x && z) || !x) && !w && y);
}int main() {
    cout << "x y z w F" << endl;
    for (int x = 0; x <= 1; ++x)
        for (int y = 0; y <= 1; ++y)
            for (int z = 0; z <= 1; ++z)
                for (int w = 0; w <= 1; ++w)
                    if (f(x, y, z, w) == true)
                        cout << x << " " << y << " "
                            << z << " " << w << " " << f(x, y, z, w) << endl;
    return 0;
}

Получили наборы:
x y z w F
0 1 0 0 1
0 1 1 0 1
1 1 1 0 1

Начинаем сопоставление с исходной тбалицей:
1) столбец без единиц четвёртый в таблице из условия — это W
2) столбец с одной единицей третий в исходной таблице — это X
3) столбей с тремя единицами — это Y
4) столбец с двумя единицами — это Z
Результат: YZXW

Ответ: yzxw

Задача 5

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

				F
0	0	0	1	0
1	0	0	1	0
1	0	1	1	0

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

Решение

bool f(int x, int y, int z, int w){
    return ((!y || w) || (!x && z));
}int main() {
    cout << "x y z w F" << endl;
    for (int x = 0; x <= 1; ++x)
        for (int y = 0; y <= 1; ++y)
            for (int z = 0; z <= 1; ++z)
                for (int w = 0; w <= 1; ++w)
                    if (f(x, y, z, w) == false)
                        cout << x << " " << y << " "
                            << z << " " << w << " " << f(x, y, z, w) << endl;
    return 0;
}

Получили наборы:
x y z w F
0 1 0 0 0
1 1 0 0 0
1 1 1 0 0

Начинаем сопоставление с исходной тбалицей:
1) столбец без единиц второй в таблице из условия — это W
2) столбец с одной единицей третий в исходной таблице — это Z
3) столбей с тремя единицами — это Y
4) столбец с двумя единицами — это X
Результат: xwzy

Ответ: xwzy

Задача 6

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

x1	x2	x3	x4	x5	x6	x7	x8	F
0	0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0	0
0	1	0	1	0	1	1	0	1
0	1	1	0	0	1	0	1	0
1	0	0	0	1	1	0	0	0
1	0	0	1	0	0	0	1	1
1	0	0	1	1	0	0	0	0
1	0	1	1	1	0	1	1	1
1	1	0	1	1	1	0	1	1
1	1	0	1	1	1	1	1	1

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

Решение

Данное выражение является конъюнкцией четырёх выражений. Конъюнкция нескольких высказываний истинна тогда и только тогда, когда истинными являются все входящие в неё высказывания. Следовательно, x₄ = 1, x₈ = 1 и в наборах значений переменных (x₁, x₂, x₃), (x₅, x₆, x₇) должна быть хотя бы одна 1.

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

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

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

Ответ: 8

Задача 7

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

Переменная 1 ???	Переменная 2 ???	Переменная 3 ???	Функция F
0	0	0	0
1	0	0	0
0	0	1	1
1	0	1	1
0	1	0	1
1	1	0	0
0	1	1	1
1	1	1	1

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

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

Переменная 1 ???	Переменная 2 ???	Функция F
1	0	0
0	1	1
0	0	1
0	1	1

Решение

Преобразуем исходное выражение.

(¬x → y) ∧ (z → y) = (x ∨ y) ∧ (¬z ∨ y) = y ∨ (x ∧ ¬z).

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

Рассмотрим строку, в которой значение функции отличается от значения переменной y. Такой строкой является четвёртая снизу. Здесь переменная y = 0, а значение функции F = 1. Это означает, что x ∧ ¬z = 1. В рассматриваемой строке значение первого столбца 0, а второго 1. Пусть x = 0, z = 1. При этих значениях логическое выражение x ∧ ¬z ложно, что не соответствует табличному значению функции F = 1. Следовательно, x = 1, z = 0. Значит, первый столбец соответствует переменной z, а второй—x.

Или при помощи программы на С++:
Выводим только ложные наборы, потому что их меньше

#include <iostream>
#include <algorithm>
#include <fstream>using namespace std;
bool f(int x, int y, int z){
    return ((x || y) && (!z || y));
}
int main() {
    cout << "x y z F" << endl;
    for (int x = 0; x <= 1; ++x)
        for (int y = 0; y <= 1; ++y)
            for (int z = 0; z <= 1; ++z)
                    if (f(x, y, z) == false)
                        cout << x << " " << y << " "
                            << z << " " << f(x, y, z) << endl;
    return 0;
}

Ответ: zxy

Задача 8

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

				F
1	0	0	0	0
1	1	0	0	0
1	1	1	0	0

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

		F
1	0	0
0	1	1
0	0	1
1	1	1

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

Задача 9

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

				F
0	0	0	1	0
1	0	0	1	0
1	0	1	1	0

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

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

		F
1	0	0
0	1	1
0	0	1
1	1	1

Задача 10

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

				F
0	1	0	0	0
0	1	0	1	0
0	1	1	1	0

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

		F
1	0	0
0	1	1
0	0	1
1	1	1

Задача 11

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

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

				F
1	1	0		0
1			1	0
		0	1	0

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

тогда 1-му столбцу соответствовала бы переменная y, а 2-му столбцу — переменная x. В ответе следовало бы написать: yx.

Задача 12

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

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

				F
1		0		0
	0		0	0
	0	1		0

Источник

В настоящее время на вступительных экзаменах
по информатике есть много заданий по теме
“алгебра логики”. Цель данного урока –
закрепление навыков решения заданий ЕГЭ по
информатике с использованием элементов алгебры
логики.

Цели урока:

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

Задачи урока:

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

Ход урока

Повторение логических операций и законов.
Применение логических операций и законов на
практике.
Объяснение домашнего задания.

Сегодня мы с вами завершаем тему “Основы
логики” и применим основные логические
операции, законы преобразования для решения
заданий ЕГЭ по информатике.

Урок идет параллельно с презентацией. <Приложение1>

1. Повторение логических операций и
законов.

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

Вопросы:

1. Основоположник формальной логики?

Аристотель.

2. Основоположник алгебры логики?

Джордж Буль.

3. Перечислите логические операции:

¬ отрицание (инверсия)
&, / конъюнкция (“И”)
V дизъюнкция (“ИЛИ”)

логическое следование (импликация)
равнозначность
(эквивалентность)

4. В чем смысл закона двойного отрицания?

Двойное отрицание исключает отрицание.

5. Законы де Моргана (законы общей инверсии).

Отрицание дизъюнкции является конъюнкцией
отрицаний:

¬(A V B) = ¬A / ¬B

Отрицание конъюнкции является дизъюнкцией
отрицаний:

¬(A /B) = ¬A V ¬B

6. Закон идемпотентности (одинаковости).

A V A = A

A / A = A

7. В чём смысл закона исключения третьего?

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

A V ¬А= 1

8. О чём закон противоречия?

Не могут быть одновременно истинны утверждение
и его отрицание:

A / ¬А= 0

9. Закон исключения констант.

Для логического сложения:

A V 1 = 1 A V 0 = A

Для логического умножения:

A / 1 = A A / 0 = 0

10. Как выразить импликацию через дизъюнкцию?

А В = ¬A V В

2. Примение логических операций и законов
на практике.

Пример 1. (Задание А11 демоверсии 2004 г.)

Для какого имени истинно высказывание:

¬ (Первая буква имени гласная -> Четвертая
буква имени согласная)?

1) ЕЛЕНА

2) ВАДИМ

3) АНТОН

4) ФЕДОР

Решение. Сложное высказывание состоит из
двух простых высказываний:

А – первая буква имени гласная,

В – четвертая буква имени согласная.

¬ (А В) = ¬ (¬A V
В) = (¬ (¬А) / ¬B) = A / ¬B

Применяемые формулы:

1. Импликация через дизъюнкцию А ? В = ¬A V В

2. Закон де Моргана ¬(A V B) = ¬A / ¬B

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

(Первая буква имени гласная / Четвертая буква
имени гласная)

Ответ: 3

Пример 2. (Задание А12 демоверсии 2004 г.)

Какое логическое выражение равносильно
выражению ¬ (А / ¬B)?

1) A / B

2) A / B

3) ¬A / ¬B

4) ¬A / B

Решение. ¬ (А / ¬B)= ¬ А / ¬ (¬B)= ¬ А / B

Ответ: 4

Пример 3.

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

¬ (B / C) V (A/C B)

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

¬ (B / C) V (A/C B)

2 1 5 3 4

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

Сколько строк будет в вашей таблице? 3
переменных: А, В, С; 2³=8

Сколько столбцов? 5 операций + 3 переменных = 8

Решение:

A	B	C	(B / C)	¬ (B / C)	A/C	(A/C ? B)	¬ (B / C) V (A/C B)
0	0	0	0	1	0	1	1
0	0	1	0	1	0	1	1
0	1	0	0	1	0	1	1
0	1	1	1	0	0	1	1
1	0	0	0	1	0	0	1
1	0	1	0	1	1	1	1
1	1	0	0	1	0	0	1
1	1	1	1	0	1	1	1

Какие ответы получились в последнем столбце?

Ответ: 1

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

Решим этот пример аналитическим методом:

упрощаем выражение

¬ (B / C) V (A/C B)=
(применим формулу для импликации)

¬ (B / C) V ¬ (A / C) V B = (применим 1 и 2 законы де
Моргана)

(¬B V ¬C) V (¬A V ¬C) V B = (уберём скобки)

¬B V ¬C V ¬A V ¬C V B= (применим переместительный
закон)

¬B V B V ¬C V ¬C V ¬A = (закон исключения третьего,
закон идемпотентности)

1 V ¬С V ¬A = 1 V ¬A = 1 (закон исключения констант)

Ответ: 1, означает, что формула является
тождественно-истинной или тавтологией.

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

(задание 3 домашнего задания)

Пример 4.

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

Для обозначения логической операции “ИЛИ” в
запросе используется символ I, а для логической
операции “И” – символ &.

А Законы & Физика

Б Законы I (Физика & Биология)

В Законы & Физика & Биология & Химия

Г Законы I Физика I Биология

Решение:

Первый способ основан на рассуждении.
Рассуждая логически, мы видим, что больше всего
будет найдено страниц по запросу Г, так как при
его исполнении будут найдены и страницы со
словом “законы”, и страницы, со словом
“физика”, и страницы со словом “биология”.
Меньше всего будет найдено страниц по запросу В,
так как в нем присутствие всех четырех слов на
искомой странице. Осталось сравнить запросы А и
Б. По запросу Б будут найдены все страницы,
соответствующие запросу А, (так как в последних
обязательно присутствует слово “законы”), а
также страницы, содержащие одновременно слова
“физика” и “биология”. Следовательно по
запросу Б будет найдено больше страниц, чем по
запросу А. Итак, упорядочив запросы по
возрастанию страниц, получаем ВАБГ.

Ответ: ВАБГ.

Второй способ предполагает использование
графического представления операций над
множествами. (Смотри презентацию)

Пример 5. (Задание А16 демоверсии 2006 г.)

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

Фамилия	Пол	Математика	Русский язык	Химия	Информатика	Биология
Аганян	ж	82	56	46	32	70
Воронин	м	43	62	45	74	23
Григорчук	м	54	74	68	75	83
Роднина	ж	71	63	56	82	79
Сергеенко	ж	33	25	74	38	46
Черепанова	ж	18	92	83	28	61

Сколько записей в данном фрагменте
удовлетворяют условию

“Пол=’м’ ИЛИ Химия>Биология”?

1) 5

2) 2

3) 3

4) 4

Решение:

Выбираем записи: Мальчики (двое) и
Химия>Биология (трое, но один мальчик, уже
взялся 1 раз). В итоге 4 записи удовлетворяют
условию.

Ответ: 4

Задание 6. (Задание В4 демоверсии 2007 г)

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

Один считает, что первой будет Наташа, а Маша
будет второй.

Другой болельщик на второе место прочит Люду, а
Рита, по его мнению, займет четвертое место.

Третий любитель тенниса с ними не согласился.
Он считает, что Рита займет третье место, а Наташа
будет второй.

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

Какое место на чемпионате заняли Наташа, Маша,
Люда, Рита?

(В ответе перечислите подряд без пробелов
числа, соответствующие местам девочек в
указанном порядке имен.)

Решение:

Обозначим высказывания:

Н1 = “первой будет Наташа”;

М2 = “второй будет Маша”;

Л2 = “второй будет Люда”;

Р4 = “четвертой будет Рита”;

Р3 = “третьей будет Рита”;

Н2 = “второй будет Наташа”.

Согласно условию:

из высказываний 1 болельщика следует, что Н1VМ2
истинно;

из высказываний2 болельщика следует, что Л2VР4
истинно;

из высказываний 3 болельщика следует, что Р3VН2
истинно.

Следовательно, истинна и конъюнкция

(Н1VМ2) / (Л2VР4) / (Р3VН2) = 1.

Раскрыв скобки получим:

(Н1VМ2) / (Л2VР4) / (Р3VН2) = (Н1/Л2V Н1/Р4 V М2/Л2 V М2/Р4) /
(Р3VН2)=

Н1/ Л2/Р3 V Н1/Р4/Р3 V М2/Л2/Р3 V М2/Р4/Р3 V Н1/Л2/Н2 V
Н1/Р4/Н2 V М2/Л2/Н2 V М2/Р4/Н2 = Н1/ Л2/Р3 V 0 V 0 V 0 V 0 V 0
V 0 V= Н1/ Л2/Р3

Наташа-1, Люда-2, Рита-3, а Маша-4.

Ответ: 1423

3. Объяснение домашнего задания.

Задание 1. (Задание В8 демоверсии 2007г)

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

Для обозначения логической операции “ИЛИ” в
запросе используется символ |, а для логической
операции “И” – &.

А волейбол | баскетбол | подача

Б волейбол | баскетбол | подача | блок

В волейбол | баскетбол

Г волейбол & баскетбол & подача

Задание 2 (Задание В4 демоверсии 2008г)

Перед началом Турнира Четырех болельщики
высказали следующие предположения по поводу
своих кумиров:

A) Макс победит, Билл – второй;

B) Билл – третий. Ник – первый;

C) Макс – последний, а первый – Джон.

Какое место на турнире заняли Джон, Ник, Билл,
Макс?

(В ответе перечислите подряд без пробелов места
участников в указанном порядке имен.)

Оценки за урок.

Источник

Информатика, 10 класс. Урок № 12.

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

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

Глоссарий по теме: основные законы алгебры логики, логические функции, дизъюнктивная и конъюнктивная нормальная форма, совершенная дизъюнктивная нормальная форма (СДНФ), совершенная конъюнктивная нормальная форма (СКНФ)

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 10 класса

— М.: БИНОМ. Лаборатория знаний, 2017 (с.197—209)

Открытые электронные ресурсы по теме:

http://lbz.ru/metodist/authors/informatika/3/eor10.php

http://kpolyakov.spb.ru/school/ege.htm

Теоретический материал для самостоятельного изучения.

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

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

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

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

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

В общем случае можно предложить следующую последовательность действий:

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

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

Здесь последовательно использованы замена операции импликация, закон де Моргана, распределительный закон, закон противоречия и операция с константой, закон идемпотентности и поглощения.

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

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

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

A, B, C — множества. Для них можно записать (U — универсальное множество).

Будем считать, что.

Тогда , причем это минимально возможное множество А.

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

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

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

Введем обозначения:

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

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

Рассмотрим предикат . В числе 45₁₀=101101₂ 5-й, 3-й, 2-й и 0-й биты содержат единицы, 4-й и 1-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 5, 3, 2 или 0 содержит единицу. Если и 5-й, и 3-й, и 2-й, и 0-й биты числа х нулевые, то высказывание будет ложным.

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

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

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

Так как , примем .

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

Искомое число a должно быть таким, чтобы при любом неотрицательном целом значении переменной х: , и, кроме того, оно должно быть минимальным из возможных. Этим условиям удовлетворяет число 101100₂= 44₁₀.

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

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

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

A	B	F₁	F₂	F₃	F₄	F₅	F₆	F₇	F₈	F₉	F₁₀	F₁₁	F₁₂	F₁₃	F₁₄	F₁₅	F₁₆
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

F₁(A,B) = 0 — константа «ложь»;

F₂(A,B) = A&B — конъюнкция;

F₃(A,B) = — отрицание импликации;

F₄(A,B) = A — функция, равная первому аргументу;

F₅(A,B) = — отрицание обратной импликации;

F₆(A,B) = B — функция, равная второму аргументу;

F₇(A,B) = — строгая дизъюнкция;

F₈(A,B) = A˅B — дизъюнкция;

F₉(A,B) = — стрелка Пирса (отрицание дизъюнкции, ИЛИ-НЕ);

F₁₀(A,B) = — эквиваленция;

F₁₁(A,B) = — отрицание второго аргумента;

F₁₂(A,B) = — обратная импликация;

F₁₃(A,B) = — отрицание первого аргумента;

F₁₄(A,B) = — импликация;

F₁₅(A,B) = — штрих Шеффера (отрицание конъюнкции, И-НЕ);

F₁₆(A,B) = 1 — константа «истина».

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

F₂ и F₁₁ (конъюнкция и отрицание второго аргумента);
F₈ и F₁₃ (дизъюнкция и отрицание первого аргумента);
F₉(стрелка Пирса, отрицание дизъюнкции);
F₁₅(штрих Шеффера, отрицание конъюнкции).

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

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

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

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

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

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

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций. Например, выражение является ДНФ.

Конъюнктивной нормальной формой (КНФ) называется конъюнкция простых дизъюнкций. Например, выражение является КНФ.

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

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

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

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

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

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

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

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

Источник

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

Алгебра логики (англ. algebra of logic) — один из основных разделов математической логики, в котором методы алгебры используются в логических преобразованиях.

Основоположником алгебры логики является английский математик и логик Дж. Буль (1815–1864), положивший в основу своего логического учения аналогию между алгеброй и логикой. Любое высказывание он записывал с помощью символов разработанного им языка и получал «уравнения», истинность или ложность которых можно было доказать, исходя из определенных логических законов, таких как законы коммутативности, дистрибутивности, ассоциативности и др.

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

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

Например, «3 умножить на 3 равно 9», «Архангельск севернее Вологды» — истинные высказывания, а «Пять меньше трех», «Марс — звезда» — ложные.

Очевидно, что не всякое предложение может быть логическим высказыванием, т. к. не всегда есть смысл говорить о его ложности или истинности. Например, высказывание «Информатика — интересный предмет» неопределенно и требует дополнительных сведений, а высказывание «Для ученика 10-А класса Иванова А. А. информатика — интересный предмет» в зависимости от интересов Иванова А. А. может принимать значение «истина» или «ложь».

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

В алгебре логики различаются простые (элементарные) высказывания, обозначаемые латинскими буквами (A, B, C, D, …), и сложные (составные), составленные из нескольких простых с помощью логических связок, например таких, как «не», «и», «или», «тогда и только тогда», «если … то». Истинность или ложность получаемых таким образом сложных высказываний определяется значением простых высказываний.

Обозначим как А высказывание «Алгебра логики успешно применяется в теории электрических схем», а через В — «Алгебра логики применяется при синтезе релейно-контактных схем».

Тогда составное высказывание «Алгебра логики успешно применяется в теории электрических цепей и при синтезе релейно-контактных схем» можно кратко записать как А и В; здесь «и» — логическая связка. Очевидно, что поскольку элементарные высказывания А и В истинны, то истинно и составное высказывание А и В.

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

Логических значений всего два: истина (TRUE) и ложь (FALSE). Это соответствует цифровому представлению — 1 и 0. Результаты каждой логической операции можно записать в виде таблицы. Такие таблицы называют таблицами истинности.

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

1. Логическое отрицание, инверсия (лат. inversion — переворачивание) — логическая операция, в результате которой из данного высказывания (например, А) получается новое высказывание (не А), которое называется отрицанием исходного высказывания, обозначается символически чертой сверху ($A↖{-}$) или такими условными обозначениями, как ¬, ‘not’, и читается: «не А», «А ложно», «неверно, что А», «отрицание А». Например, «Марс — планета Солнечной системы» (высказывание А); «Марс — не планета Солнечной системы» ($A↖{-}$); высказывание «10 — простое число» (высказывание В) ложно; высказывание «10 — не простое число» (высказывание B ) истинно.

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

A	¬A
истина	ложь
ложь	истина

или

Высказывание $A↖{-}$ ложно, когда А истинно, и истинно, когда А ложно.

Геометрически отрицание можно представить следующим образом: если А — это некоторое множество точек, то $A↖{-}$ — это дополнение множества А, т. е. все точки, которые не принадлежат множеству А.

2. Конъюнкция (лат. conjunctio — соединение) — логическое умножение, операция, требующая как минимум двух логических величин (операндов) и соединяющая два или более высказываний при помощи связки «и» (например, «А и В»), которая символически обозначается с помощью знака ∧ (А ∧ В) и читается: «А и В». Для обозначения конъюнкции применяются также следующие знаки: А ∙ В; А & В, А and В, а иногда между высказываниями не ставится никакого знака: АВ. Пример логического умножения: «Этот треугольник равнобедренный и прямоугольный». Данное высказывание может быть истинным только в том случае, если выполняются оба условия, в противном случае высказывание ложно.

Таблица истинности операции имеет вид

A	B	A ∧ B
истина	ложь	ложь
ложь	истина	ложь
ложь	ложь	ложь
истина	истина	истина

или

A	B	A ∧ B
1	0	0
0	1	0
0	0	0
1	1	1

Высказывание А ∧ В истинно только тогда, когда оба высказывания — А и В истинны.

Геометрически конъюнкцию можно представить следующим образом: если А, В — это некоторые множества точек, то А ∧ В есть пересечение множеств А и В.

3. Дизъюнкция (лат. disjunction — разделение) — логическое сложение, операция, соединяющая два или более высказываний при помощи связки «или» (например, «А или В»), которая символически обозначается с помощью знака ∨ (А ∨ В) и читается: «А или В». Для обозначения дизъюнкции применяются также следующие знаки: А + В; А or В; А | B. Пример логического сложения: «Число x делится на 3 или на 5». Это высказывание будет истинным, если выполняются оба условия или хотя бы одно из условий.

Таблица истинности операции имеет вид

A	B	A ∨ B
истина	ложь	истина
ложь	истина	истина
ложь	ложь	ложь
истина	истина	истина

или

A	B	A ∨ B
1	0	1
0	1	1
0	0	0
1	1	1

Высказывание А ∨ В ложно только тогда, когда оба высказывания — А и В ложны.

Геометрически логическое сложение можно представить следующим образом: если А, В — это некоторые множества точек, то А ∨ В — это объединение множеств А и В, т. е. фигура, объединяющая и квадрат, и круг.

4. Дизъюнкция строго-разделительная, сложение по модулю два — логическая операция, соединяющая два высказывания при помощи связки «или», употребленной в исключающем смысле, которая символически обозначается с помощью знаков ∨ ∨ или ⊕ (А ∨ ∨ В, А ⊕ В) и читается: «либо А, либо В». Пример сложения по модулю два — высказывание «Этот треугольник тупоугольный или остроугольный». Высказывание истинно, если выполняется какое-то одно из условий.

Таблица истинности операции имеет вид

А	В	А ⊕ B
истина	ложь	истина
ложь	истина	истина
ложь	ложь	ложь
истина	истина	ложь

или

А	В	А ⊕ B
1	0	1
0	1	1
0	0	0
1	1	0

Высказывание А ⊕ В истинно только тогда, когда высказывания А и В имеют различные значения.

5. Импликация (лат. implisito — тесно связываю) — логическая операция, соединяющая два высказывания при помощи связки «если…, то» в сложное высказывание, которое символически обозначается с помощью знака → (А → В) и читается: «если А, то В», «А влечет В», «из А следует В», «А имплицирует В». Для обозначения импликации применяется также знак ⊃ (A ⊃ B). Пример импликации: «Если полученный четырехугольник квадрат, то около него можно описать окружность». Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием. Результат операции ложен только тогда, когда предпосылка есть истина, а следствие — ложь. Например, «Если 3 * 3 = 9 (А), то Солнце — планета (В)», результат импликации А → В — ложь.

Таблица истинности операции имеет вид

А	В	А → В
истина	ложь	ложь
ложь	истина	истина
ложь	ложь	истина
истина	истина	истина

или

А	В	А → В
1	0	0
0	1	1
0	0	1
1	1	1

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

6. Эквивалентность, двойная импликация, равнозначность (лат. aequalis — равный и valentis — имеющий силу) — логическая операция, позволяющая из двух высказываний А и В получить новое высказывание А ≡ В, которое читается: «А эквивалентно B». Для обозначения эквивалентности применяются также следующие знаки: ⇔, ∼. Эта операция может быть выражена связками «тогда и только тогда», «необходимо и достаточно», «равносильно». Примером эквивалентности является высказывание: «Треугольник будет прямоугольным тогда и только тогда, когда один из углов равен 90 градусам».

Таблица истинности операции эквивалентности имеет вид

А	В	А ∼ В
истина	ложь	ложь
ложь	истина	ложь
ложь	ложь	истина
истина	истина	истина

или

А	В	А ∼ В
1	0	0
0	1	0
0	0	1
1	1	1

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

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

Сложение по модулю два	А ⊕ В	$(A↖{-} ∧B) ∧ (A ∧ B↖{-})$
Импликация	А → В	$A↖{-} ∨ B$
Эквивалентность	А ∼ В	$(A↖{-} ∧ B↖{-}) ∨ (A ∧ B)$

Приоритет выполнения логических операций следующий: отрицание («не») имеет самый высокий приоритет, затем выполняется конъюнкция («и»), после конъюнкции — дизъюнкция («или»).

С помощью логических переменных и логических операций любое логическое высказывание можно формализовать, т. е. заменить логической формулой. При этом элементарные высказывания, образующие составное высказывание, могут быть абсолютно не связаны по смыслу, но это не мешает определять истинность или ложность составного высказывания. Например, высказывание «Если пять больше двух (А), то вторник всегда наступает после понедельника (В)» — импликация А → В, и результат операции в данном случае — «истина». В логических операциях смысл высказываний не учитывается, рассматривается только их истинность или ложность.

Рассмотрим, например, построение составного высказывания из высказываний А и В, которое было бы ложно тогда и только тогда, когда оба высказывания истинны. В таблице истинности для операции сложения по модулю два находим: 1 ⊕ 1 = 0. А высказывание может быть, например, таким: «Этот мяч полностью красный или полностью синий». Следовательно, если утверждение А «Этот мяч полностью красный» — истина, и утверждение В «Этот мяч полностью синий» — истина, то составное утверждение — ложь, т. к. одновременно и красным, и синим мяч быть не может.

Примеры решения задач

Пример 1. Определить для указанных значений X значение логического высказывания ((X > 3) ∨ (X < 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

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

A	B	A → B
1	0	0
0	1	1
0	0	1
1	1	1

Отсюда получаем:

1) для X = 1:

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

2) для X = 12:

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

3) для X = 3:

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Пример 2. Указать множество целых значений X, для которых истинно выражение ¬((X > 2) → (X > 5)) .

Решение. Операция отрицания применена ко всему выражению ((X > 2) → (X > 5)) , следовательно, когда выражение ¬((X > 2) → (X > 5)) истинно, выражение ((X > 2) →(X > 5)) ложно. Поэтому необходимо определить, для каких значений X выражение ((X > 2) → (X > 5)) ложно. Операция импликации принимает значение «ложь» только в одном случае: когда из истины следует ложь. А это выполняется только для X = 3; X = 4; X = 5.

Пример 3. Для каких из приведенных слов ложно высказывание ¬(первая буква гласная ∧ третья буква гласная) ⇔ строка из 4 символов? 1) асса; 2) куку; 3) кукуруза; 4) ошибка; 5) силач.

Решение. Рассмотрим последовательно все предложенные слова:

1) для слова асса получим: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

2) для слова куку получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

3) для слова кукуруза получим: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 — высказывание ложно;

4) для слова ошибка получим: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 — высказывание истинно;

5) для слова силач получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 — высказывание ложно.

Логические выражения и их преобразование

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

выражения, которые используют операции сравнения («больше», «меньше», «равно», «не равно» и т. п.) и принимают логические значения (например, выражение а > b , где а = 5 и b = 7, равно значению «ложь»);
непосредственные логические выражения, связанные с логическими величинами и логическими операциями (например, A ∨ В ∧ С, где А = истина, B = ложь и C = истина).

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

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

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

Пример. Найти значение выражения:

$1 ≤ a ∨ A ∨ sin(π/a — π/b) < 1 ∧ ¬B ∧ ¬(b^a + a^b > a + b ∨ A ∧ B)$ для а = 2, b = 3, A = истина, В = ложь.

Решение. Порядок подсчета значений:

1) b^a + a^b > a + b, после подстановки получим: 3² + 2³ > 2 + 3, т. е. 17 > 2 + 3 = истина;

2) A ∧ B = истина ∧ ложь = ложь.

Следовательно, выражение в скобках равно (b^a + a^b > a + b ∨ A ∧ B) = истина ∨ ложь = истина;

3) 1≤ a = 1 ≤ 2 = истина;

4) sin(π/a — π/b) < 1 = sin(π/2 — π/3) < 1 = истина.

После этих вычислений окончательно получим: истина ∨ А ∧ истина ∧ ¬В ∧ ¬истина.

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

5) ¬В = ¬ложь = истина; ¬истина = ложь;

6) A ∧ истина ∧ истина ∧ ложь = истина ∧ истина ∧ истина ∧ ложь = ложь;

7) истина ∨ ложь = истина.

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

Примечание. Учитывая, что исходное выражение есть, в конечном итоге, сумма двух слагаемых, и значение одного из них 1 ≤ a = 1 ≤ 2 = истина, без дальнейших вычислений можно сказать, что результат для всего выражения тоже «истина».

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

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

Закон	Для ∨	Для ∧
Переместительный	A ∨ B = B ∨ A	A ∧ B = B ∧ A
Сочетательный	A ∨ (B ∨ C) = (B ∨ A) ∨ C	A ∧ (B ∧ C) = (A ∧ B) ∧ C
Распределительный	A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C)	A ∨ B ∧ C = (A ∨ B) ∧ (A ∨ C)
Правила де Моргана	${A ∨ B}↖{-}$ = $A↖{-} ∧ B↖{-}$	${A ∧ B}↖{-}$ = $A↖{-} ∨ B↖{-}$
Идемпотенции	A ∨ A = A	A ∧ A = A
Поглощения	A ∨ A ∧ B = A	A ∧ (A ∨ B) = A
Склеивания	(A ∧ B) ∨ (A↖{-} ∧ B) = B	(A ∨ B) ∧ (A↖{-} ∨ B) = B
Операция переменной с ее инверсией	$A ∨ A↖{-}$ = 1	$A ∧ A↖{-}$ = 0
Операция с константами	A ∨ 0 = A A ∨ 1 = 1	A ∧ 1 = A A ∧ 0 = 0
Двойного отрицания	$A↖{=}$ = A

Доказательства этих утверждений производят на основании построения таблиц истинности для соответствующих записей.

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

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

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

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

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

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1 .

Здесь для упрощения применяется закон поглощения.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

При преобразовании применяются правило де Моргана, операция переменной с ее инверсией, операция с константой

Примеры решения задач

Пример 1. Найти логическое выражение, равносильное выражению A ∧ ¬(¬B ∨ C) .

Решение. Применяем правило де Моргана для В и С: ¬(¬B ∨ C) = B ∧ ¬C .

Получаем выражение, равносильное исходному: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

Ответ: A ∧ B ∧ ¬C.

Пример 2. Указать значение логических переменных А, В, С, для которых значение логического выражения (A ∨ B) → (B ∨ ¬C ∨ B) ложно.

Решение. Операция импликации ложна только в случае, когд а из истинной посылки следует ложь. Следовательно, для заданного выражения посылка A ∨ B должна принимать значение «истина», а следствие, т. е. выражение B ∨ ¬C ∨ B , — «ложь».

1) A ∨ B — результат дизъюнкции — «истина», если хотя бы один из операндов — «истина»;

2) B ∨ ¬C ∨ B — выражение ложно, если все слагаемые имеют значение «ложь», т. е. В — «ложь»; ¬C — «ложь», а следовательно, переменная С имеет значение «истина»;

3) если рассмотреть посылку и учесть, что В — «ложь», то получим, что значение А — «истина».

Ответ: А — истина, В — ложь, С — истина.

Пример 3. Каково наибольшее целое число X, при котором истинно высказывание (35 < X · X) → (X < (X — 3)) ?

Решение. Запишем таблицу истинности для операции импликации:

A	B	A → B
1	0	0
0	1	1
0	0	1
1	1	1

Выражение X < (X — 3) ложно при любых положительных значениях X. Следовательно, для того чтобы результатом импликации была «истина», необходимо и достаточно, чтобы выражение 35 < X · X также было ложно. Максимальное целое значение X, для которого 35 < X · X ложно, равно 5.

Ответ: X = 5.

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

Логические выражения могут быть использованы для описания геометрических областей. В этом случае задача формулируется так: записать для заданной геометрической области такое логическое выражение, которое принимает значение «истина» для значений x, y тогда и только тогда, когда любая точка с координатами (x; y) принадлежит геометрической области.

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

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

1) .

Решение. Заданную геометрическую область можно представить в виде набора следующих областей: первая область — D1 — полуплоскость ${x}/{-1} +{y}/{1} ≤ 1$, вторая — D2 — круг с центром в начале координат $x^2 + y^2 ≤ 1$. Их пересечение D1 $∩$ D2 представляет собой искомую область.

Результат: логическое выражение ${x}/{-1}+{y}/{1} ≤ 1 ∧ x^2 + y^2 ≤ 1$.

Эту область можно записать так: |x| ≤ 1 ∧ y ≤ 0 ∧ y ≥ -1 .

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

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

Пример 2. Нарисовать и заштриховать область, для точек которой выполняется логическое условие y ≥ x ∧ y + x ≥ 0 ∧ y < 2 .

Решение. Искомая область представляет собой пересечение трех полуплоскостей. Строим на плоскости (x, y) прямые y = x; y = –x; y = 2. Это границы области, причем последняя граница y = 2 не принадлежит области, поэтому ее наносим пунктирной линией. Для выполнения неравенства y ≥ x нужно, чтобы точки находились слева от прямой y = x, а неравенство y = –x выполняется для точек, которые находятся справа от прямой y = –x. Условие y < 2 выполняется для точек, лежащих ниже прямой y = 2. В результате получим область, которая изображена на рис.:

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

Логические функции очень удобны для описания работы электрических схем. Так, для схемы, представленной на рис., где значение переменной X — это состояние выключателя (если он включен, значение X — «истина», а если выключен — «ложь»), это значение Y — это состояние лампочки (если она горит — значение «истина», а если нет — «ложь»), логическая функция запишется так: Y = X . Функцию Y называют функцией проводимости.

Для схемы, представленной на рис., логическая функция Y имеет вид: Y = X1 ∪ X2, т. к. достаточно одного включенного выключателя, чтобы горела лампочка. В схеме на рис., для того чтобы горела лампочка, должны быть включены оба выключателя, следовательно, функция проводимости имеет вид: Y = X1 ∧ X2 .

Для более сложной схемы функция проводимости будет иметь вид: Y = (X11 ∨ (X12 ∧ X13)) ∧ X2 ∧ (X31 ∨ X32).

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

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

Использование аппарата алгебры логики при проектировании логических схем

Математический аппарат алгебры логики очень удобен для описания того, как функционируют аппаратные средства компьютера. Любая информация при обработке на компьютере представляется в двоичной форме, т. е. кодируется некоторой последовательностью 0 и 1. Обработку двоичных сигналов, соответствующих 0 и 1, выполняют в компьютере логические элементы. Логические элементы, которые выполняют основные логические операции И, ИЛИ, НЕ, представлены на рис.

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

Технически компьютерный логический элемент реализуется в виде электрической схемы, которая представляет собой соединение различных деталей: диодов, транзисторов, резисторов, конденсаторов. На вход логического элемента, который называют также вентилем, поступают электрические сигналы высокого и низкого уровней напряжения, на выход выдается один выходной сигнал также либо высокого, либо низкого уровня. Эти уровни соответствуют одному из состояний двоичной системы: 1 — 0; ИСТИНА — ЛОЖЬ. Каждый логический элемент имеет свое условное обозначение, которое выражает его логическую функцию, но не указывает на то, какая именно электронная схема в нем реализована. Это упрощает запись и понимание сложных логических схем. Работу логических схем описывают с помощью таблиц истинности. Условное обозначение на схеме ИЛИ знак «1» — от устаревшего обозначения дизъюнкции как «>=1» (значение дизъюнкции равно 1, если сумма двух операндов больше или равна 1). Знак «&» на схеме И является сокращенной записью английского слова and.

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

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

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

Удобной формой записи при нахождении значений функции является таблица, содержащая, кроме значений переменных и значений функции, также значения промежуточных вычислений. Рассмотрим пример построения таблицы истинности для формулы ${X1}↖{-} ∧ X2 ∨ {X1 ∨ X2}↖{-} ∨ X1$.

X1	X2	${X1}↖{-}$	${X1}↖{-}$ X2	X1 ∧ X2	${X1 ∨ X2}↖{-}$	${X1}↖{-}$ ∧ X2 ∨ ${X1 ∨ X2}↖{-}$	${X1}↖{-}$ ∧ X2 ∨ ${X1 ∨ X2}↖{-}$ ∨ X1
1	1	0	0	1	0	0	1
1	0	0	0	1	0	0	1
0	1	1	1	1	0	1	1
0	0	1	0	0	1	1	1

Если функция принимает значение 1 при всех наборах значений переменных, она является тождественно-истинной; если при всех наборах входных значений функция принимает значение 0, она является тождественно-ложной; если набор выходных значений содержит как 0, так и 1, функция называется выполнимой. Приведенный выше пример является примером тождественно-истинной функции.

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

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

Алгоритм построения ДНФ следующий:

в таблице истинности функции выбирают наборы аргументов, для которых логические формы равны 1 («истина»);
все выбранные логические наборы как логические произведения аргументов записывают, последовательно соединив их между собой операцией логической суммы (дизъюнкции);
для аргументов, которые являются ложными, в построенной записи проставляют операцию отрицания.

Пример. Построить функцию, определяющую, что первое число равно второму, используя метод ДНФ. Таблица истинности функции имеет вид

X1	X2	F(X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

Решение. Выбираем наборы значений аргументов, в которых функция равна 1. Это первая и четвертая строки таблицы (строку заголовка при нумерации не учитываем).

Записываем логические произведения аргументов этих наборов, объединив их логической суммой: X1 ∧ X2 ∨ X1 ∧ X2 .

Записываем отрицание относительно аргументов выбранных наборов, имеющих ложное значение (четвертая строка таблицы; второй набор в формуле; первый и второй элементы): X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

Ответ: F(X1, X2) = X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

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

Алгоритм построения КНФ следующий:

в таблице истинности выбирают наборы аргументов, для которых логические формы равны 0 («ложь»);
все выбранные логические наборы как логические суммы аргументов записывают последовательно, соединив их между собой операцией логического произведения (конъюнкции);
для аргументов, которые являются истинными, в построенной записи проставляют операцию отрицания.

Примеры решения задач

Пример 1. Рассмотрим предыдущий пример, т. е. построим функцию, определяющую, что первое число равно второму, используя метод КНФ. Для заданной функции ее таблица истинности имеет вид

X1	X2	F(X1, X2)
1	1	1
0	1	0
1	0	0
0	0	1

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

Записываем логические суммы аргументов этих наборов, объединив их логическим произведением: X1 ∨ X2 ∧ X1 ∨ X2 .

Записываем отрицание относительно аргументов выбранных наборов, имеющих истинное значение (вторая строка таблицы, первый набор формулы, второй элемент; для третьей строки, а это второй набор формулы, первый элемент): X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2.

Таким образом, получена запись логической функции в КНФ.

Ответ: X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2.

Полученные двумя методами значения функций являются эквивалентными. Для доказательства этого утверждения используем правила логики: F(X1, X2) = X1 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ X2 = X1 ∧ ${X1}↖{-}$ ∨ X1 ∧ X2 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ ${X2}↖{-}$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ ${X2}↖{-}$ ∧ ${X1}↖{-}$ ∨ 0 = X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ ${X2}↖{-}$.

Пример 2. Построить логическую функцию для заданной таблицы истинности:

X1	X2	F(X1, X2)
1	1	1
1	0	0
0	1	1
0	0	0

Решение. Используем алгоритм ДНФ для построения исходной функции:

X1	X2	F(X1, X2)
1	1	1	•	X1 ∧ X2
1	0	0
0	1	1	•	${X1}↖{-}$ ∧ X2
0	0	0

Искомая формула: X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ X2 .

Ее можно упростить: X1 ∧ X2 ∨ ${X1}↖{-}$ ∧ X2 = X2 ∧ (X1 ∨ ${X1}↖{-}$) = X2 ∧ 1 = X2.

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

X1	X2	X3	F(X1, X2, X3)
1	1	1	1	•	X1 ∧ X2 ∧ X3
1	0	1	0
0	1	1	1	•	${X1}↖{-}$ ∧ X2 ∧ X3
0	0	1	0
1	1	0	1	•	X1 ∧ X2 ∧ ${X3}↖{-}$
1	0	0	1	•	X1 ∧ ${X2}↖{-}$ ∧ ${X3}↖{-}$
0	1	0	0
0	0	0	0

Искомая формула: X1 ∧ X2 ∧ X ∨ ${X1}↖{-}$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ ${X3}↖{-}$ ∪ X1 ∧ ${X2}↖{-}$ ∧ ${X3}↖{-}$.

Формула достаточно громоздка, и ее следует упростить:

X1 ∧ X2 ∧ X3 ∨ ${X1}↖{-}$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ ${X3}↖{-}$ ∨ X1 ∧ ${X2}↖{-}$ ∧ ${X3}↖{-}$ = X2 ∧ X3 ∧ (X1 ∨ ${X1}↖{-}$) ∨ X1 ∧ ${X3}↖{-}$ ∧ (X2 ∨ ${X2}↖{-}$) = X2 ∧ X3 ∨ X1 ∧ ${X3}↖{-}$.

Таблицы истинности для решения логических задач

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

Примеры решения задач

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

Решение. Очевидно, что результатом решения будет таблица, в которой искомая функция Y(X1, X2, X3) будет иметь значение «истина», если какие-либо две переменные имеют значение «истина».

X1	X2	X3	Y(X1, X2, X3)
1	1	1	0
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	1
0	1	0	0
0	0	1	0
0	0	0	0

Пример 2. Составить расписание уроков на день, учитывая, что урок информатики может быть только первым или вторым, урок математики — первым или третьим, а физики — вторым или третьим. Возможно ли составить расписание, удовлетворив всем требованиям? Сколько существует вариантов расписания?

Решение. Задача легко решается, если составить соответствующую таблицу:

	1-й урок	2-й урок	3-й урок
Информатика	1	1	0
Математика	1	0	1
Физика	0	1	1

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

математика, информатика, физика;
информатика, физика, математика.

Пример 3. В спортивный лагерь приехали трое друзей — Петр, Борис и Алексей. Каждый из них увлекается двумя видами спорта. Известно, что таких видов спорта шесть: футбол, хоккей, лыжи, плавание, теннис, бадминтон. Также известно, что:

Борис — самый старший;
играющий в футбол младше играющего в хоккей;
играющие в футбол и хоккей и Петр живут в одном доме;
когда между лыжником и теннисистом возникает ссора, Борис мирит их;
Петр не умеет играть ни в теннис, ни в бадминтон.

Какими видами спорта увлекается каждый из мальчиков?

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

Так как видов спорта шесть, получается, что все мальчики увлекаются разными видами спорта.

Из условия 4 следует, что Борис не увлекается ни лыжами, ни теннисом, а из условий 3 и 5, что Петр не умеет играть в футбол, хоккей, теннис и бадминтон. Следовательно, любимые виды спорта Петра — лыжи и плавание. Занесем это в таблицу, а оставшиеся клетки столбцов «Лыжи» и «Плавание» заполним нулями.

	Футбол	Хоккей	Лыжи	Плавание	Бадминтон	Теннис
Петр	0	0	1	1	0	0
Борис			0	0		0
Алексей			0	0

Из таблицы видно, что в теннис может играть только Алексей.

Из условий 1 и 2 следует, что Борис не футболист. Таким образом, в футбол играет Алексей. Продолжим заполнять таблицу. Внесем в пустые ячейки строки «Алексей» нули.

	Футбол	Хоккей	Лыжи	Плавание	Бадминтон	Теннис
Петр	0	0	1	1	0	0
Борис	0		0	0		0
Алексей	1	0	0	0	0	1

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

	Футбол	Хоккей	Лыжи	Плавание	Бадминтон	Теннис
Петр	0	0	1	1	0	0
Борис	0	1	0	0	1	0
Алексей	1	0	0	0	0	1

Ответ: Петр увлекается лыжами и плаванием, Борис играет в хоккей и бадминтон, а Алексей занимается футболом и теннисом.

Источник

x1	x2	x3	x4	x5	x6	x7	x8	F
0	0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0	0
0	1	0	1	0	1	1	0	1
0	1	1	0	0	1	0	1	0
1	0	0	0	1	1	0	0	0
1	0	0	1	0	0	0	1	1
1	0	0	1	1	0	0	0	0
1	0	1	1	1	0	1	1	1
1	1	0	1	1	1	0	1	1
1	1	0	1	1	1	1	1	1

А	Законы & Физика
Б	Законы I (Физика & Биология)
В	Законы & Физика & Биология & Химия
Г	Законы I Физика I Биология

А	волейбол \| баскетбол \| подача
Б	волейбол \| баскетбол \| подача \| блок
В	волейбол \| баскетбол
Г	волейбол & баскетбол & подача

x1	x2	x3	x4	x5	x6	x7	x8	F
0	0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0	0
0	1	0	1	0	1	1	0	1
0	1	1	0	0	1	0	1	0
1	0	0	0	1	1	0	0	0
1	0	0	1	0	0	0	1	1
1	0	0	1	1	0	0	0	0
1	0	1	1	1	0	1	1	1
1	1	0	1	1	1	0	1	1
1	1	0	1	1	1	1	1	1

x1	x2	x3	x4	x5	x6	x7	x8	F
0	0	0	1	0	0	0	1	0
0	1	0	0	0	1	0	0	0
0	1	0	1	0	1	1	0	1
0	1	1	0	0	1	0	1	0
1	0	0	0	1	1	0	0	0
1	0	0	1	0	0	0	1	1
1	0	0	1	1	0	0	0	0
1	0	1	1	1	0	1	1	1
1	1	0	1	1	1	0	1	1
1	1	0	1	1	1	1	1	1