Меню

Какому логическому выражению соответствует следующая таблица истинности инверсия

 

Какому логическому выражению соответствует следующая таблица истинности инверсия

Логическая функция 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.

Источник

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

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

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

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

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

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

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

A

B

А&В

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

A

B

A \/ B

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

A

¬ А

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

A

B

A B

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

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

A

B

A

B

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

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

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

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

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

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

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

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

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

x1

x2

x3

x4

x5

x6

F

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

x1

x2

x3

x4

x5

x6

x7

F

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте также:  Таблица токов и сечений кабелей 380

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

Источник

Таблица истинности

  • Что такое таблицы истинности
  • Логические операции
  • Логические выражения
  • Инверсия
  • Конъюнкция
  • Дизъюнкция
  • Правила составления таблицы истинности
  • Примеры построения таблицы истинности

Что такое таблицы истинности

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

Таблица истинности необходима для совершения логических операций. Она включает в себя n+1 столбцы и 2 n строки, где n — число используемых переменных. В первых n столбцах представлены разные значения аргументов функции, а в n+1 столбце представлены значения функции, которые она принимает на данном наборе аргументов.

Набором называется совокупность значений переменных. А = 0, В = 1. В случае, когда количество переменных n, число различных наборов будет равно 2 N . Например, для трех переменных число разных наборов будет равно 2 3 = 8.

Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.

Для создания таблиц истинности используются обозначения логических значений 0 (ложь) и 1 (истина).

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

Применение таблиц истинности чаще всего встречается в булевой алгебре и в цифровой электронной технике для описания работы логических схем.

Логические операции

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

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

К логическим операциям относятся конъюнкция, дизъюнкция, импликация, разделительная дизъюнкция, эквиваленция, антиконъюнкция, антидизъюнкция.

Логические выражения

Логическое выражение — это запись, принимающая логическое значение «истина» или «ложь».

Их можно разделить на два типа:

    выражения, использующие операции сравнения и принимающие логические значения. Например, выражение a Определение

Инверсия или логическое отрицание — это логическая операция, при выполнении которой из данного высказывания получается новое высказывание. Это высказывание является отрицанием исходного высказывания.

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

Конъюнкция

Конъюнкция — это логическое умножение. Эта операция, для которой требуются два и более логических величины. Конъюнкция соединяет логические высказывания при помощи связки «и». Связка изображается символом ∧.

Конъюнкция может быть истинной только в том случае, если оба высказывания истинны. Например, A ∧ B, если A = ложь, а B = истина, является ложным.

Дизъюнкция

Дизъюнкция — логическое сложение. Эта логическая операция соединяет два и более высказываний с помощью связки «или». Эта связка обозначается как ∨.

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

Правила составления таблицы истинности

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

Строить таблицы истинности необходимо по следующему алгоритму:

  1. Вычислить число переменных в выражении (n).
  2. Вычислить общее количество логических операций в выражении.
  3. Определить последовательность, в которой будут выполняться логические операции.
  4. Установить количество столбцов в таблице — количество переменных и количество операций.
  5. Внести в шапку таблицы переменные и операции, соблюдая последовательность, определенную в пункте 3.
  6. Высчитать количество строк в таблице, используя формулу m = 2 n
  7. Занести в таблицу наборы входных переменных. Они представляют собой целый ряд n-разрядных двоичных чисел от 0 до 2 n −1.
  8. Заполнить таблицу, совершая логические операции.
Читайте также:  Таблица эксель с данными фио

Примеры построения таблицы истинности

Задача

Построим таблицу истинности и решим выражение \( F = (A \vee B) \wedge (¬A \vee ¬B)\) . Будем пользоваться приведенным выше алгоритмом.

  1. Число переменных в выражении n = 2.
  2. Общее количество логических операций в выражении — 5.
  3. Последовательность выполнения логических операций — 1, 5, 2, 4, 3.
  4. Количество столбцов — 7. Логические переменные (А и В) + логические операции \(\vee\) , \(\wedge\) , \(¬\) , \(\vee\) , \(¬\) = 2 +5 = 7.
  5. Количество строк — 5, исходя из m =2 n , таким образом 2 2 = 4, 4+1 (строка заголовков столбцов) = 5.
  6. Заполним таблицу.

Решение

А В \(А \vee В\) ¬А ¬В \(¬А \vee ¬В\) \((A \vee B) \wedge (¬A \vee ¬B)\)
1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1

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

F = 0 при A = B = 0 и A = B = 1

Задача

Построим еще одну таблицу истинности и решим выражение \(F = X \vee Y \wedge ¬Z\)

  1. Число переменных в выражении n = 3.
  2. Общее количество логических операций в выражении — 3.
  3. Последовательность выполнения логических операций — 3, 2, 1.
  4. Количество столбцов — 6. Логические переменные (X, Y, Z) + логические операции \( \vee\) , \(\wedge\) , ¬ = 3 + 3 = 6.
  5. Количество строк — 9, исходя из m =2 n , таким образом 2 3 = 8, 8+1 (строка заголовков столбцов) = 9.
  6. Заполним таблицу.

Решение

X Y Z ¬ Z \(Y \wedge ¬Z\) \(X \vee Y \wedge ¬Z\)
q
1
1 1 1 1
1 1 1
1 1 1
1 1 1 1 1
1 1 1 1

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

F = 0, при X = Y = Z = 0; при X = Y = 0 и Z = 1.

Источник

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

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

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

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

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

Отрицание

Отрицание и инверсия — самое простое логическое преобразование. Ему соответствует частица «не.» Это преобразование просто меняет утверждение на противоположное. Соответственно, значение утверждения тоже меняется на противоположное. Если утверждение А истинно, то «не А» — ложно. Например, утверждение «прямой угол — это угол, равный девяносто градусов» — истина. Тогда его отрицание «прямой угол не равен девяноста градусам» — ложь.

Таблица истинности для отрицания будет такова:

Конъюнкция

Конъюнкция аналогична умножению и соответствует союзу «и». Такое выражение будет верно, только если верны все утверждения, объединённые конъюнкцией. То есть, утверждение «А и Б» будет истинным, только если А — истина и Б — истина. Во всех остальных случаях выражение «А и Б» ложно. Например, высказывание «Земля круглая и плоская» будет ложно, так как первая часть истина, а вторая — ложь.

Источник

Adblock
detector