Меню

Выполнимой формула какая таблица истинности



Логические формулы и таблицы истинности

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

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

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

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

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

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

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

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

Рассмотрим следующее рассуждение: Владимир Маяковский родился в 1891 году или в 1893 году; Однако известно, что он родился не в 1891 году; Следовательно он родился в 1893 году. Формализуя это рассуждение, выделим входящие в него простые высказывания:

  1. Владимир Маяковский родился в 1891 году;
  2. Владимир Маяковский родился в 1893 году.

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

Количество строк в таблице определяется по правилу 2n, где n – количество переменных (простых высказываний) в формуле. Поскольку в нашей формуле только две переменных (а и в), то в таблице должно быть четыре строки (не считая, конечно же, верхнюю строчку, которая является так называемой «шапкой» таблицы). Количество колонок в таблице равно сумме числа переменных и числа логических союзов, входящих в формулу. В рассматриваемой формуле две переменных (а и в) и четыре логических союза ( , , ¬, ?), т. е. в таблице должно быть шесть колонок.

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

Третья колонка – это истинностные значения строгой дизъюнкции (а в), которые она принимает в зависимости от всех (четырех) наборов истинностных значений переменных.
Четвертая колонка – это истинностные значения отрицания первого простого высказывания (¬ а).

Пятая колонка – это истинностные значения конъюнкции, состоящей из вышеуказанной строгой дизъюнкции и отрицания ((а в) ¬ а), и наконец, шестая колонка – это истинностные значения всей формулы или импликации (((а в) ¬ а) ? в).

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

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

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

Строгая дизъюнкция (а в) и отрицание (¬ а), образующие данную конъюнкцию, одновременно истинны только в одном случае, следовательно конъюнкция ((а в) ¬ а) один раз принимает значение «истинно», а в остальных случаях – «ложно». Наконец, надо заполнить последнюю колонку для импликации (((а в) ¬ а) ? в), которая и будет представлять истинностные значения всей формулы.
Возвращаясь к базисной таблице истинности сложных суждений, вспомним, что импликация ложна только в од- ном случае, когда ее основание истинно, а следствие лож- но. Основанием нашей импликации является конъюнкция ((а в) ¬ а), представленная в пятой колонке таблицы, а следствием является простое суждение (в), представленное во второй колонке. (Некоторое неудобство в данном случае составляет то, что слева направо следствие идет раньше основания, однако мы всегда можем мысленно поменять их местами). В первом случае (первая строчка таблицы, не считая «шапки») основание импликации ложно, а следствие истинно, значит, импликация истинна. Во втором случае и

Читайте также:  Производительные силы общества таблица

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

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

Рассмотрим еще один пример. Требуется формализовать следующее рассуждение и установить, к какому виду относится выражающая его формула: Если какое-либо здание является старым, то оно нуждается в капитальном ремонте; Это здание нуждается в капитальном ремонте; Следовательно это здание старое.

Выделим простые высказывания, входящие в это рассуждение:

  1. Какое-либо здание является старым;
  2. Какое-либо здание нуждается в капитальном ремонте.

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

Чтобы определить вид получившейся формулы, составим таблицу ее истинности. В формуле две переменных (а и в), значит в таблице будет четыре строчки (не считая верхней); также в формуле три союза (?, , ?), значит в таблице будет пять колонок. Первые две колонки – это истинностные значения переменных. Третья колонка – истинностные значения импликации (а ? в). Четвертая колонка – истинностные значения конъюнкции ((а ? в) в). Пятая, последняя колонка – истинностные значения всей формулы – итоговой импликации (((а ? в) в) ? а).

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

Как видим, рассматриваемая формула принимает как значение «истинно», так и значение «ложно» при различных на- борах истинностных значений входящих в нее переменных, следовательно, она является выполнимой или нейтральной, а рассуждение, формализацией которого она выступает, логи- чески неверно, или неправильно: при ином содержании рас- суждения такая форма его построения могла бы привести к ошибке. (Например: Если слово стоит в начале предложения, то оно пишется с большой буквы; Слово «Москва» всегда пишется с большой буквы; Следовательно, слово «Москва» всегда стоит в начале предложения).
Мы рассмотрели формулы, состоящие из двух переменных, в силу чего в таблицах их истинности было по 22 = 4 строчки, обозначающие все возможные наборы (см. первые две колонки вышеприведенных таблиц) истинностных значений переменных:

  1. обе истинны;
  2. одна истинна, другая ложна;
  3. одна ложна, другая истинна;
  4. обе ложны.

В этом случае заполнить первые две колонки таблицы истинности очень просто. Но как это сделать, если в формулу будут входить три переменных и количество строчек в таблице истинности для такой формулы будет равно 23 = 8, или если переменных будет четыре, а строчек в таблице, соответственно, – 16 и т. д.?

Чтобы ответить на этот вопрос, посмотрим как заполняются первые две колонки в таблице с четырьмя строчками: в первой колонке два раза пишется «истинно», а потом два раза «ложно»; во второй колонке пишется один раз «истинно», один раз «ложно», потом опять «истинно» и еще раз «ложно».

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

Источник

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

Инструкция . При вводе с клавиатуры используйте следующие обозначения:

Клавиша Оператор
! ¬ Отрицание (НЕ)
| | Штрих Шеффера (И-НЕ)
# Стрелка Пирса (ИЛИ-НЕ)
* & Конъюнкция (И)
+ v Дизъюнкция (ИЛИ)
^ Исключающее ИЛИ, сумма по модулю 2 (XOR)
@ Импликация (ЕСЛИ-ТО)
% Обратная импликация
= ≡ (

bc необходимо ввести так: a*b*c+a*b=c+a=b*c
Для ввода данных в виде логической схемы используйте этот сервис.

Правила ввода логической функции

  1. Вместо символа v (дизъюнкция, ИЛИ) используйте знак + .
  2. Перед логической функцией не надо указывать обозначение функции. Например, вместо F(x,y)=(x|y)=(x^y) необходимо ввести просто (x|y)=(x^y) .
  3. Максимальное количество переменных равно 10 .

Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики — алгебры логики. В алгебре логики можно выделить три основные логические функции: «НЕ» (отрицание), «И» (конъюнкция), «ИЛИ» (дизъюнкция).
Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики.
Функция алгебры логики называется полностью определённой если заданы все 2 n её значения, где n – число выходных переменных.
Если определены не все значения, функция называется частично определённой.
Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики.
Для представления функции алгебры логики используется следующие способы:

  • словесное описание – это форма, которая используется на начальном этапе проектирования имеет условное представление.
  • описание функции алгебры логики в виде таблицы истинности.
  • описание функции алгебры логики в виде алгебраического выражения: используется две алгебраические формы ФАЛ:
    а) ДНФ – дизъюнктивная нормальная форма – это логическая сумма элементарных логических произведений. ДНФ получается из таблицы истинности по следующему алгоритму или правилу:
    1) в таблице выбираются те строки переменных для которых функция на выходе =1 .
    2) для каждой строки переменных записывается логическое произведение; причём переменные =0 записываются с инверсией.
    3) полученное произведение логически суммируется.
    Fднф= X 123 ∨ Х1 x 2Х3 ∨ Х1Х2 x 3 ∨ Х1Х2Х3
    ДНФ называется совершенной, если все переменные имеют одинаковый ранг или порядок, т.е. в каждое произведение обязательно должны включаться все переменные в прямом или инверсном виде.
    б) КНФ – конъюнктивная нормальна форма – это логическое произведение элементарных логических сумм.
    КНФ может быть получена из таблицы истинности по следующему алгоритму:
    1) выбираем наборы переменных для которых функция на выходе =0
    2) для каждого набора переменных записываем элементарную логическую сумму, причём переменные =1 записываются с инверсией.
    3) логически перемножаются полученные суммы.
    Fскнф=(X1 V X2 V X3) ∧ (X1 V X2 V X 3) ∧ (X1 V X 2 V X3) ∧ ( X 1 V X2 V X3)
    КНФ называется совершенной, если все переменные имеют одинаковый ранг.

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

Рисунок1- Схема логического устройства

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

Источник

Логические выражения и таблица истинности

Таблица истинности — таблица, показывающая, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний.

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

Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак « =».

Алгоритм построения таблицы истинности:

1. подсчитать количество переменных n в логическом выражении;

2. определить число строк в таблице по формуле m=2 n , где n — количество переменных;

3. подсчитать количество логических операций в формуле;

4. установить последовательность выполнения логических операций с учетом скобок и приоритетов;

5. определить количество столбцов: число переменных + число операций;

6. выписать наборы входных переменных;

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

1. разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»;

2. разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»;

3. продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа.

Пример 1. Для формулы A/\ (B \/ ¬B /\ ¬C) постройте таблицу истинности.

Количество логических переменных 3, следовательно, количество строк — 2 3 = 8.

Количество логических операций в формуле 5, количество логических переменных 3, следовательно количество столбцов — 3 + 5 = 8.

Пример 2. Определите истинность логического выражения F(А, В) = (А\/ В)/\(¬А\/¬В) .

1. В выражении две переменные А и В (n=2).

2. m строк=2 n , m=2 2 =4 строки.

3. В формуле 5 логических операций.

4. Расставляем порядок действий

1) А\/ В; 2) ¬А; 3) ¬В; 4) ¬А\/¬В; 5) (А\/ В)/\(¬А\/¬В).

5. К столбцов=n+5=2+5=7 столбцов.

Вывод: логическое выражение принимает значение истина при наборах F(0,1)=1 и F(1,0)=1.

Пример 3. Построёте таблицу истинности для логического выражения

  1. В данной функции три логические переменные – А, В, С
  2. количество строк таблицы = 2 3=8
  3. В формуле 3 логические операции.
  4. Расставляем порядок действий
  1. количество столбцов таблицы = 3 + 3 = 6

Пример 4. Определите истинность формулы: F = ((С \/В) => В) /\ (А /\ В) => В.

Построим таблицу истинности этой формулы.

Ответ: формула является тождественно истинной.

Пример 5. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.

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

Какое выражение соответствует F?

Решение (вариант 1, через таблицы истинности ):

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

Очевидно, что значения заданной функции F совпадают со значениями выражения X\/ Y\/¬ Z. Следовательно, правильный ответ – 3.

Решение (Вариант 2):

Чтобы не строить таблицу истинности для каждого выражения, можно просто перепроверить предложенные ответы по заданной таблице истинности. Т.е. в каждую из четырех предложенных функций последовательно подставлять значения переменных X, Y и Z, из заданной таблицы истинности и вычислять значения логического выражения. Если значения вычисляемого выражения совпадут со значением F во всех трех строчках заданной таблицы, то это и есть искомое выражение.

Рассмотрим данный конкретный пример:

1) первое заданное выражение ¬X/\¬Y/\Z = 0 при X=0, Y=0, Z=0, что не соответствует первой строке таблицы;

2) второе заданное выражение ¬X\/¬Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы;

3) третье выражение X\/Y\/¬Z соответствует F при всех предложенных комбинациях X,Y и Z;

4) четвертое выражение X\/Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы.

Источник

Таблица истинности онлайн с примерами — логика

Таблица истинности — это таблица, которая описывает логическую функцию. Логическая функция здесь — это функция, у которой значения переменных и значение самой функции выражают истинность. Например, они принимают значения «истина» либо «ложь» (true либо false, 1 либо 0).

Таблицы истинности применяются для определения значения какого-либо высказывания для всех возможных случаев значений истинности высказываний, которые его составляют. Количество всех существующих комбинаций в таблице находится по формуле N=2*n; где N — общее количество возможных комбинаций, n — число входных переменных. Таблицы истинности нередко используются в цифровой технике и булевой алгебре, чтобы описать работу логических схем.

Таблицы истинности для основных функций

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

Примеры: конъюнкция — 1&0=0, импликация — 1→0=0.

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

Инверсия; Конъюнкция; Дизъюнкция; Импликация; Эквиваленция; Штрих Шеффера; Стрелка Пирса.

Последовательность построения (составления) таблицы истинности:

  1. Определить количество N используемых переменных в логическом выражении.
  2. Вычислить количество всевозможных наборов значений переменных M = 2 N , равное количеству строк в таблице.
  3. Подсчитать количество логических операций в логическом выражении и определить количество столбцов в таблице, которое равно количеству переменных плюс количество логических операций.
  4. Озаглавить столбцы таблицы названиями переменных и названиями логических операций.
  5. Заполнить столбцы логических переменных наборами значений, например, от 0000 до 1111 с шагом 0001 в случае для четырех переменных.
  6. Заполнить таблицу истинности по столбцам со значениями промежуточных операций слева направо.
  7. Заполнить окончательный столбец значений для функции F.

Таким образом, можно составить (построить) таблицу истинности самостоятельно.

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

Заполните поле ввода и нажмите OK. T — истина, F — ложь. Рекомендуем добавить страницу в закладки или сохранить в социальной сети.

Обозначения

  1. Множества или выражения большими буквами латинского алфавита: A, B, C, D.
  2. A’ — штрих — дополнения множеств
  3. && — конъюнкция («и»)
  4. || — дизъюнкция («или»)
  5. ! — отрицание (например, !A)
  6. \cap — пересечение множеств \cap
  7. \cup — объединение множеств (сложение) \cup
  8. A&!B — разность множеств A∖B=A-B
  9. A=>B — импликация «Если . то»
  10. A B — эквивалентность

Всё для учебы » Математика в школе » Таблица истинности онлайн с примерами — логика

Чтобы добавить страницу в закладки, нажмите Ctrl+D.

Если страница помогла, сохраните её и поделитесь ссылкой с друзьями:

Источник

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

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

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

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

Таблица истинности необходима для совершения логических операций. Она включает в себя 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