Главная страница

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


Скачать 2.43 Mb.
НазваниеАнализ таблиц истинности логических выражений
Дата16.03.2022
Размер2.43 Mb.
Формат файлаdoc
Имя файлаege2.doc
ТипДокументы
#399283
страница2 из 32
1   2   3   4   5   6   7   8   9   ...   32

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


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

(xy)  ¬(yz)  ¬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 = 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. заполняем первую часть таблицы, перечисляя все комбинации переменных в порядке возрастания двоичного кода:



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



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



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



  1. дальше рассуждаем так же, как и при теоретическом решении

  2. Ответ: 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

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

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

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

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

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

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

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

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

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

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

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

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

print(x, y, z, w)

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

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)

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

x y z w

0 1 0 0

1 0 1 0

1 1 0 0

  1. дальше рассуждаем так же, как и в приведённом выше теоретичеком решении

  2. Ответ: zyxw.

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

  1. в принципе, можно написать программу, которая сразу выдает решение этого задания прямым перебором вариантов

  2. Часть 1: https://www.youtube.com/watch?v=yX5oSYtM5E0

  3. Часть 2: https://www.youtube.com/watch?v=eSkrt4KrsmU

  4. Ответ: zyxw.
1   2   3   4   5   6   7   8   9   ...   32


написать администратору сайта