Таблица истинности для строгой дизъюнкции

Таблица истинности для строгой дизъюнкции

Сейчас мы познакомимся с шестью основными логическими операциями. Каждая из них имеет несколько названий и обозначений.

Названия операции

Возможные обозначения

Конъюнкция, логическое умножение, операция И, операция AND.

`&, ^^, *,` по аналогии с алгебраическим умножением может никак не обозначаться

Дизъюнкция, нестрогая дизъюнкция, логическое сложение, операция ИЛИ, операция OR.

Строгая дизъюнкция, разделительная дизъюнкция, исключающее ИЛИ, сложение по модулю `2`.

Эквивалентность, эквиваленция, равенство, равнозначность.

Импликация, следование, следствие

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

Для того, чтобы не путаться и гарантированно перебрать все возможные комбинации значений операндов, принято записывать их в лексикографическом порядке (условно считается, что «ложь» ` bbq` или `bbq ->bbp`?) Импликация ложна только в единственном случае: когда левый операнд имеет значение «истина», а правый – «ложь». Рассмотрим все возможные значения операндов и проанализируем, какая из ситуаций невозможна.

1) `p` и `q` ложны. Это значит, что четырёхугольник не является квадратом и его стороны не равны. Это возможная ситуация.

2) `p` – ложно, `q` – истинно. Это значит, что четырёхугольник не является квадратом, но стороны у него равны. Это возможно (ромб).

3) `p` – истинно, `q` – истинно. Это значит, что четырёхугольник является квадратом и стороны у него равны. Это возможная ситуация.

4) `p` – истинно, `q` – ложно. Это значит, что четырёхугольник является квадратом, но стороны у него не равны. Это невозможная ситуация.

Анализ ситуаций показывает, что левым операндом импликации должна быть переменная `p`. Таким образом, в формализованном виде исходное высказывание выглядит как `bb(p -> q)` .

Очень часто вместо «присвоим логическим переменным эти высказывания» говорят «обозначим высказывания следующим образом». В дальнейшем мы тоже будем использовать этот речевой оборот.

Источник



Разделительные суждения Полная и неполная, строгая и слабая дизъюнкция. Таблицы истинности для дизъюнкции.

Разделительные (дизъюнктивные) суждения.

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

Если первое обозначить В, а второе — С, то разделительное суждение символически можно выразить как В v С, где В и С — члены дизъюнкции (дизъюнкты), v — символ дизъюнкции.

Разделительное суждение может быть как двух-, так и многосоставным: В v С v . v п.

Таблицы истинности для сложных высказываний:

Строгой Не строгой

Условные суждения. Таблица истинности для импликации.

3. Условные (импликативные) суждения.

Условным, или импликативным, называют суждение, состоящее из двух простых, связанных логической связкой «если. то. ». Например: «Если предохранитель плавится, то электролампа гаснет». Первое суждение — «Предохранитель плавится» называют антецедентом (предшествующим), второе — «Электролампа гаснет» —консеквентом (последующим). Если антецедент обозначить А, консеквент — В, а связку «если. то. » знаком «>», то импликативное суждение символически можно выразить какА>В.

Для импликации

Эквивалентные суждения. Таблица истинности для двойной импликации.

Эквивалентные суждения (двойная импликация). Эквивалентным называют суждение, включающее в качестве составных два суждения, связанных двойной (прямой и обратной) условной зависимостью, выражаемой логической связкой «если и только если—, то. ». Например: «Если и только если человек награжден орденами и медалями «А», то он имеет право на ношение соответствующих орденских планок «В».

Логическая характеристика этого суждения состоит в том, что истинность утверждения о награждении «А» рассматривается как необходимое и достаточное условие истинности утверждения о наличии права на ношение орденских планок «В» Точно так же истинность утверждения о наличии права на ношение орденских планок В является необходимым и достаточным условием истинности ут­верждения о том, что данное лицо награждено соответствующими орденом или медалью А. Такую обоюдную зависимость символически можно выразить двойной импликацией А(Стрелочка влево и стрелочка вправо)q, которая читается: «Если и только если А, то В». Эквивалентность выражают и другим знаком:А = В(Вместо 2х линий 3).

Для эквиваленции

В шапках таблиц – высказывания или их субъекты и предикаты. Буква «и» — истинно; буква «л» — ложно; «?» — неизвестно, зависит от конкретной ситуации.

Значки — отношения: /\— конъюнкция (соединение); \/— дизъюнкция (разделение);>— импликация (условность); — эквиваленция (двусторонняя зависимость).

Суждения с отношениями.

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

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

Не всякое сложное суждение выражается сложным предложением, но всякое сложное предложение выражает сложное суждение.

Выделяют следующие виды сложных суждений: 1)соединительные (конъюнкция);

2) разделительные (дизъюнкция);

3) условные (импликация);

4) эквивалентные. Конъюнкция – образуется из нескольких простых,

связанных логической связкой «и». Например, «Никто не забыт и ничто не забыто» – А В. (Где А – Никто не забыт; В – ничто не забыто. А и В – члены конъюнкции).

Для конъюнкции свойственна взаимозаменяемость положения членов конъюнкции: А В, или В А.

Дизъюнкция состоит из нескольких простых, связанных логической связкой «или»: А V В.

Выделяют две разновидности разделительного суждения:

1) нестрогую (слабую) дизъюнкцию;

2) строгую (сильную) дизъюнкцию.

Слабая дизъюнкция – объединяемые ею суждения не исключают друг друга, т. е. вместо «или» можно поставить «и» (символ V). Слабая дизъюнкция истинна в тех случаях, когда истинно одно из суждений (или оба), и ложна, когда оба суждения ложны.

Сильная дизъюнкция – образуется логической связкой «либо», и ее составляющие исключают друг друга. Строгая дизъюнкция истинна только тогда, когда одно из суждений истинно, а другое – ложно.

Импликация – суждения объединяются на основе логической связки «если. то», например: «Если будет хорошая погода, то соревнования состоятся».

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

Между сложными суждениями существуют определенные отношения, они могут быть совместимыми и несовместимыми.

Совместимые суждения – это суждения, которые могут быть одновременно истинными.

Выделяют три вида совместимости сложных суждений:

2) частичная совместимость;

Эквивалентными являются суждения, являющиеся истинными или ложными одновременно.

Частично совместимыми являются суждения, которые могут быть одновременно истинными, но не могут быть одновременно ложными.

К подчиненным относятся такие суждения, в которых при истинности подчиняющего подчиненное всегда истинно.

Суждения, которые одновременно не могут быть истинными, являются несовместимыми.

Выделяют два вида несовместимости: 1) противоположность; 2) противоречие.

Противоположность – отношение между суждениями, которые одновременно не могут быть истинными, но могут быть одновременно ложными.

Противоречащими являются суждения, которые не могут быть одновременно истинными и ложными.

Источник

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

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

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 ₁*Х₂*Х₃ ∨ Х₁ x ₂Х₃ ∨ Х₁Х₂ x ₃ ∨ Х₁Х₂Х₃
  ДНФ называется совершенной, если все переменные имеют одинаковый ранг или порядок, т.е. в каждое произведение обязательно должны включаться все переменные в прямом или инверсном виде.
  б) КНФ – конъюнктивная нормальна форма – это логическое произведение элементарных логических сумм.
  КНФ может быть получена из таблицы истинности по следующему алгоритму:
  1) выбираем наборы переменных для которых функция на выходе =0
  2) для каждого набора переменных записываем элементарную логическую сумму, причём переменные =1 записываются с инверсией.
  3) логически перемножаются полученные суммы.
  Fскнф=(X₁ V X₂ V X₃) ∧ (X₁ V X₂ V X ₃) ∧ (X₁ V X ₂ V X₃) ∧ ( X ₁ V X₂ V X₃)
  КНФ называется совершенной, если все переменные имеют одинаковый ранг.

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

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

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Таблица истинности для строгой дизъюнкции

Если высказывание A истинно, будем писать A =1, а если — ложно, то A =0.

Значения логической функции для разных сочетаний значений входных переменных — или наборов входных переменных — обычно задаются специальной таблицей. Такая таблица называется таблицей истинности (комбинационной таблицей). Количество наборов входных переменных (Q) можно определить по формуле:Q=2n, где n — количество входных переменных.

Простейшим примером логической функции является функция одной переменной:

• F 0 (X) — константа 0;
• F₁(X) — переменная X;
• F₂(X) — инверсия X;
• F₃(X) — константа 1.

Рассмотрим таблицу значений функции от n переменных. Число строк в такой таблице будет равно числу всевозможных n -ок, т.е. равно 2 n . А число столбцов – числу переменных плюс единица, т.е. ( n +1). При построении таблицы учтем, что каждую n можно рассматривать как двоичное число, и выпишем их в порядке возрастания от 0 до 2 n –1.

В правом столбце таблицы записывают значения функции на соответствующих n -ках.

Тождественно-истинные функции – это логические функции, истинные на всех наборах значений входных переменных.

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

Источник