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

• Название: Анализ таблиц истинности логических выражений
• Дата: 10.09.2022
• Размер: 2.49 Mb.
• Имя файла: ege2.doc
• Тип: Документы; #670447
• страница: 2 из 34

Пример задания:

Р-22 (демо-2021). Логическая функция F задаётся выражением

(x  y)  ¬(y  z)  ¬w.

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

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

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

Решение (построение таблицы истинности для F = 1):

1. 
   перепишем выражения в виде
   
2. 
   поскольку имеем логическое произведение значение w обязательно должно быть равно 0, то есть, в столбце w таблицы должны быть все нули; это возможно только в последнем столбце:
   

   ?	?	?	w	F
   1		1	0	1
   0	1		0	1
   	1	1	0	1

3. 
   теперь определим все комбинации переменных, для которых функция равна 1 (их не должно быть много!)
   
4. 
   чаще всего в выражении встречается переменная y, поэтому мы сначала примем y = 0, а затем – y = 1.
   
5. 
   при y = 0 (и w = 0) получаем , что справедливо только при x = 1и z = 1:
   

   x	y	z	w	F
   1	0	1	0	1

6. 
   при y = 1 (и w = 0) получаем , что справедливо при z = 0 и любом x, это даёт ещё два варианта:
   

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

7. 
   объединим три полученных строки:
   

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

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

   z	?	?	w	F
   1		1	0	1
   0	1		0	1
   0	1	1	0	1

9. 
   при z = 1нужно, чтобы y = 0, поэтому второй столбец – это y, а третий – x:
   

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

10. 
    Ответ: zyxw.
    

Решение (построение таблицы с помощью электронных таблиц, П.Е. Финкель, г. Тимашевск)

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

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

4. 
   сортируем строки таблицы по столбцу H по убываниию:
   

5. 
   удаляем строки, где функция равна 0; можно также скрыть вспомогательные столбцы E, F, G:
   

6. 
   дальше рассуждаем так же, как и при теоретическом решении
   
7. 
   Ответ: zyxw.
   

Решение (построение таблицы с помощью программы, А.С. Гусев, г. Москва, https://youtu.be/RRL1Wal9ImU):

1. 
   поскольку во время компьютерного экзамена есть возможность использовать среды программирования, для построения частичной таблицы истинности (всех строк, при которых F=1) можно написать переборную программу на Python
   
2. 
   перебор выполняем во вложенном цикле:
   

for x in 0, 1:

for y in 0, 1:

for z in 0, 1:

for w in 0, 1:

# вычисление функции F

# вывод (x, y, z, w), если F=1

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

∧ конъюнкция and

для языков, где логическое значение True воспринимается как 1, а False – как 0, можно использовать обычное умножение *

∨ дизъюнкция or

¬ отрицания not()

≡ тождество ==

⊕ строгая дизъюнкция !=

→ импликация – для импликации в python оператора нет, но импликацию можно преобразовать в дизъюнкцию; например, a → b можно записать как ¬a ∨ b, а это в свою очередь записать как not(a)or b, not a or b или a <= b

4. 
   Запишем нашу функцию на языке программирования:
   

F = (x or y) and not(y == z) and not(w)

5. 
   чтобы выводить не полную таблицу истинности, а только те строки, в которых функция равна 1, добавим условие вывода:
   

if F: # то же самое, что "if F == True:"

print(x, y, z, w)

6. 
   Приведём полную программу:
   

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 = (x or y) and not(y == z) and not(w)

if F:

print(x, y, z, w)

7. 
   после запуска программы получаем все интересующие нас строки:
   

x y z w

0 1 0 0

1 0 1 0

1 1 0 0

8. 
   дальше рассуждаем так же, как и в приведённом выше теоретичеком решении
   
9. 
   Ответ: zyxw.
   

Решение (прямой перебор, А. Богданов):

1. 
   в принципе, можно написать программу, которая сразу выдает решение этого задания прямым перебором вариантов
   
2. 
   Часть 1: https://www.youtube.com/watch?v=yX5oSYtM5E0
   
3. 
   Часть 2: https://www.youtube.com/watch?v=eSkrt4KrsmU
   
4. 
   Ответ: zyxw.