Меню

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



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

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

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

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

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

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

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

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

Источник

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

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

Переменная 1 Переменная 2 Переменная 3 Переменная 4 Функция
1 1 1
1 1
1 1 1

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

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

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

Значение выражения всегда ложно тогда, когда переменная w равна 1, следовательно, столбцы, в которых содержится единица, не могут соответствовать переменной w, то есть переменной w соответствует четвёртый столбец.

Чтобы выражение было истинным, переменная z или переменная y должна принимать значение 0. Значит, в первом столбце в третьей строке должен стоять 0. Из третьей строки заключим, что переменные y и z должны соответствовать первому и второму столбцам таблицы. Если переменная y будет соответствовать первому столбцу, а переменная z — второму, то во второй строке выражение окажется ложным, поскольку переменная x в третьем столбце второй строки должна быть равна 0, чтобы строки таблицы истинности не повторялись. Тогда y соответствует второму столбцу, а z — первому. Значит, третьему столбцу соответствует переменная x.

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

Приведем другое решение.

Составим таблицу истинности для выражения (xy) ∧ ¬(yz) ∧ ¬w и выпишем те наборы переменных, при которых данное выражение равно 0. В наборах переменные запишем в порядке х, y, z, w. Получим следующие наборы:

Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.

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

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

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

Тогда первый столбец соответствует переменной z.

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

Читайте также:  Торонто Монреаль кленовые листья оправдают статус фаворитов

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

Заметим, что чтобы выражение было истинным, достаточно, если выражения во всех скобках будут истинными.

Рассмотрим первую строку таблицы истинности. Для того чтобы первая скобка была истинной, переменная y должна быть равна единице. Тогда скобка (y ≡ ¬z) будет принимать значение 1 только при z = 0. Значит, переменной z соответствует третий столбец таблицы истинности.

Рассмотрим вторую строку таблицы истинности. Переменная z = 1, тогда скобка (y ≡ ¬z) будет принимать значение истинности только при y = 0. Чтоб скобка (xy) принимала значение 1, x не должна равняться 1. Значит, переменной w соответствует второй столбец таблицы.

Рассмотрим третью строку таблицы истинности. Предположим, что первому столбцу таблицы истинности соответствует переменная x, тогда выражение может быть истинным только при x = 1, y = 1, z = 0, w = 1, но такой набор соответствует первой строке таблицы, а строки не должны повторяться. При любых других значениях, стоящих в остальных столбцах, значение выражения будет ложным. Следовательно, первому столбцу соответствует переменная y, а четвёртому — переменная x.

Приведем другое решение.

Составим таблицу истинности для выражения (xy) ∧ (y ≡ ¬z) ∧ (zw) и выпишем те наборы переменных, при которых данное выражение равно 1. В наборах переменные запишем в порядке х, y, z, w. Получим следующие наборы:

(0, 0, 1, 0), (0, 0, 1, 1), (0, 1, 0, 1), (1, 1, 0, 1).

Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.

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

Рассмотрим вторую строку таблицы истинности. В ней переменная z равна 1, и есть еще одна переменная, равная 1, следовательно, вторая строка может соответствовать только набору (0, 0, 1, 1), тогда второй столбец соответствует переменной w.

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

Тогда первый столбец — это у, а четвертый столбец — это x.

Источник

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

  • Главная
  • ЕГЭ
    • Вопросы и ответы
    • Перевод баллов
    • Соответствие заданий
  • Ваши задания
  • Учебники
    • Программирование
      • Типы данных Pascal
      • Математические функции
    • Основы логики
      • Логические операции
      • Приоритет операций
      • Законы логики
    • Системы счисления
      • О системах счисления
      • Перевод чисел
      • Таблица триад и тетрад
  • Видеоуроки
    • Досрочный-2016
    • Демо-2016
    • Досрочный-2015
    • Алгебра логики
  • Онлайн-тесты
    • Вариант 1
    • Вариант 2
    • Вариант 3
    • Вариант 4
    • Вариант 5
    • Вариант 6
    • Вариант 7
    • Вариант 8
    • Вариант 9
    • Вариант 10
  • Программы
    • Степени двойки
    • IP, маска и адрес сети
    • Решатор 5
    • Решатор 13
  • Словарь
  • 1 Системы счисления
  • 2 Таблицы истинности
  • 3 Поиск кратчайшего пути
  • 4 Базы данных
    Файловая система
  • 5 Кодирование информации
  • 6 Анализ алгоритмов
  • 7 Электронные таблицы
  • 8 Программирование: циклы
  • 9 Объем информации
    Передача информации
  • 10 Комбинаторика
  • 11 Рекурсивные алгоритмы
  • 12 Сети, адресация
  • 13 Количество информации
  • 14 Алгоритмы с исполнителем
  • 15 Поиск путей в графе
  • 16 Системы счисления
  • 17 Запросы для поисковых систем
  • 18 Логические выражения
    Отрезки, множества, функции
  • 19 Программирование: массивы
  • 20 Программирование: циклы
  • 21 Программирование: подпрограммы
  • 22 Перебор вариантов
  • 23 Системы логических уравнений
  • 24 Программирование: поиск ошибки в программе
  • 25 Программирование: обработка массивов
  • 26 Теория игр
  • 27 Программирование: разработка программы
Читайте также:  Шифр Гронсфельда или полиалфавитная замена

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

x1 x2 x3 x4 x5 x6 x7 F
1 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
  • Решение:

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

    То есть ответы 2 и 4 однозначно не подходят, и мы можем проверить только варианты с конъюнкцией.

    Проверим первое выражение по последней (единственно истинной) строке таблицы. Так как выражение является конъюнкцией, то для получения истины все переменные в выражении должны быть истинны. Для первого выражение это условие не выполняется, так как ¬x1 изменит 1 в таблице на 0, х2 в таблице ложно, ¬x7 изменит 1 в таблице на 0.

    Остаётся единственным возможным ответ 3, но для уверенности лучше проверить и его:

    x1 в таблице истинно, x2 в таблице ложно, но в выражении эта переменная отрицается, x4 в таблице ложно, но в выражении эта переменная отрицается, x7 в таблице истинно.

    Источник

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

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

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

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

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

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

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

    A

    B

    А&В

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

    A

    B

    A \/ B

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

    A

    ¬ А

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

    A

    B

    A B

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

    A

    B

    A

    B

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

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

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

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

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

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

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

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

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

    x1

    x2

    x3

    x4

    x5

    x6

    F

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

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

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

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

    Читайте также:  Cisco размер таблицы mac адресов

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

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

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

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

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

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

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

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

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

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

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

    x1

    x2

    x3

    x4

    x5

    x6

    x7

    F

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Источник