Построение логического отрицания правило

Построение логического отрицания правило — В правах

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

Обозначение: &, $\wedge$, $\cdot$.

Таблица истинности для конъюнкции

Рисунок 1.

Свойства конъюнкции:

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

Дизъюнкция или логическое сложение (в теории множеств это объединение)

Дизъюнкция является сложным логическим выражением, которое истинно практически всегда, за исключением, когда все выражения ложны.

Ничего непонятно?

Попробуй обратиться за помощью к преподавателям

Обозначение: +, $\vee$.

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

Рисунок 2.

Свойства дизъюнкции:

1. Если хотя бы одно из подвыражений дизъюнкции истинно на некотором наборе значений переменных, то и вся дизъюнкция принимает истинное значение для данного набора подвыражений.
2. Если все выражения из некоторого списка дизъюнкции ложны на некотором наборе значений переменных, то и вся дизъюнкция этих выражений тоже ложна.
3. Значение всей дизъюнкции не зависит от порядка записи подвыражений (как в математике – сложение).

Отрицание, логическое отрицание или инверсия (в теории множеств это отрицание)

Отрицание – означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО и в итоге получаем, что если исходное выражение истинно, то отрицание исходного – будет ложно и наоборот, если исходное выражение ложно, то его отрицание будет истинно.

Обозначения: не $A$, $\bar{A}$, $¬A$.

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

Рисунок 3.

Свойства отрицания:

«Двойное отрицание» $¬¬A$ является следствием суждения $A$, то есть имеет место тавтология в формальной логике и равно самому значению в булевой логике.

Импликация или логическое следование

Импликация – это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть, данная логическая операция связывает два простых логических выражения, из которых первое является условием ($A$), а второе ($A$) является следствием условия ($A$).

Обозначения: $\to$, $\Rightarrow$.

Таблица истинности для импликации

Рисунок 4.

Свойства импликации:

1. $A \to B = ¬A \vee B$.
2. Импликация $A \to B$ ложна, если $A=1$ и $B=0$.
3. Если $A=0$, то импликация $A \to B$ истинна при любом значении $B$, (из лжи может следовать истинна).

Эквивалентность или логическая равнозначность

Эквивалентность – это сложное логическое выражение, которое истинно на равных значениях переменных $A$ и $B$.

Обозначения: $\leftrightarrow$, $\Leftrightarrow$, $\equiv$.

Таблица истинности для эквивалентности

Рисунок 5.

Свойства эквивалентности:

1. Эквивалентность истинна на равных наборах значений переменных $A$ и $B$.
2. КНФ $A \equiv B = (\bar{A} \vee B) \cdot (A \cdot \bar{B})$
3. ДНФ $A \equiv B = \bar{A} \cdot \bar{B} \vee A \cdot B$

Строгая дизъюнкция или сложение по модулю 2 ( в теории множеств это объединение двух множеств без их пересечения)

Строгая дизъюнкция истинна, если значения аргументов не равны.

Для функции трёх и более переменных результат выполнения операции будет истинным только тогда, когда количество аргументов равных $1$, составляющих текущий набор — нечетное. Такая операция естественным образом возникает в кольце вычетов по модулю 2, откуда и происходит название операции.

Обозначения: $A \oplus B$ (в языках программирования), $A≠B$, $A \wedge B$ (в языках программирования).

Таблица истинности для операции сложения по модулю два

Рисунок 6.

Свойства строгой дизъюнкции:

• $a \oplus 0 = a$(идемпотентность)
• $a \oplus 1 = \bar{a}$(отрицание)
• $a \oplus a = 0$(получение 0)
• $a \oplus b = b \oplus a$(коммутативность)
• $(a \oplus b) \oplus c = a \oplus (b \oplus c)$(ассоциативность)
• $(a \oplus b) \oplus b = a$(поглощение)
• $\bar{a} \oplus b = a \oplus \bar{b} = (a \equiv b)$(сравнения по модулю)

Стрелка Пирса

Бинарная логическая операция, булева функция над двумя переменными. Названа в честь Чарльза Пирса и введена в алгебру логики в $1880—1881$ гг.

Обозначения: $\downarrow$ , ИЛИ-НЕ

Таблица истинности для стрелки Пирса

Рисунок 7.

Свойства:

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

$X \downarrow X = ¬X$— отрицание

$(X \downarrow Y) \downarrow (X \downarrow Y) \equiv X \vee Y$ — дизъюнкция

$(X \downarrow X) \downarrow (Y \downarrow Y) \equiv X \wedge Y$ — конъюнкция

$((X \downarrow X) \downarrow Y) \downarrow ((X \downarrow X) \downarrow Y) = X \to Y$ — импликация

В электронике стрелка Пирса представлена в виде элемента, который носит название «операция 2ИЛИ-НЕ» (2-in NОR).

Штрих Шеффера

Булева функция двух переменных или бинарная логическая операция. Введена в рассмотрение Генри Шеффером в 1913 г.

Обозначения: $|$, эквивалентно операции И-НЕ.

Таблицей истинности для функции штрих Шеффера

Рисунок 8.

Свойства:

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

$X \mid X = ¬X$ — отрицание

$(X \mid Y) \mid (X \mid Y) = (X \wedge Y)$ — конъюнкция

$(X \mid X) \mid (Y \mid Y) = X \vee Y$ — дизъюнкция

$X \mid ¬X$ — константа 1

Для электроники это означает, что реализация схем возможна с использованием одного типового элемента (правда это дорогостоящий элемент).

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

1. Инверсия(отрицание);
2. Конъюнкция (логическое умножение);
3. Дизъюнкция и строгая дизъюнкция (логическое сложение);
4. Импликация (следствие);
5. Эквивалентность (тождество).

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

Общие свойства

Для набора из $n$ логических переменных существует ровно $2n$ различных значений. Таблица истинности для логического выражения от $n$ переменных содержит $n+1$ столбец и $2n$ строк.

Источник: https://spravochnick.ru/informatika/algebra_logiki_logika_kak_nauka/logicheskie_operacii_i_ih_svoystva/

§ 3. Логика высказываний — Информатика. 7 класс

sh: 1: –format=html: not found

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

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

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

Еще Аристотель заметил, что правильность рассуждений не зависит от содержания, а определяется формой.

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

3.1. Понятие высказывания

Высказывание — повествовательное предложение (утверждение), о котором в настоящее время можно сказать, истинно оно или ложно (пример 3.1).

Об истинности высказывания можно говорить только в настоящем времени: высказывание «Идет дождь» может быть истинным сейчас и ложным через час.

Как правило, высказывания обозначают заглавными латинскими буквами. Если высказывание А истинно, пишут А = 1, если ложно — А = 0 (пример 3.2). Часто используют такие обозначения: А = true (истина) и А = false (ложь).

Пример 3.1. Следующие предложения являются высказываниями:

1. Атом водорода самый легкий (истинно).
2. Клетка — часть атома (ложно).
3. Кирилл Туровский — известный английский писатель и оратор (ложно).
4. При делении любого числа (кроме нуля) на само себя получается число 1 (истинно).

Пример 3.2.

А = «а0 равно 1»;

В = «Масса измеряется в литрах».

Для приведенного примера А = 1, В = 0.

3.2. Логическая операция НЕ

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

Логическая операция НЕ (отрицание) меняет значение высказывания на противоположное: истинно на ложно, а ложно на истинно.

Логическое отрицание получается из высказывания путем добавления частицы «не» к сказуемому или с использованием оборота «неверно, что…» (пример 3.3). Иногда при построении отрицаний некоторые слова заменяют их антонимами, если это возможно.

Любую операцию над числами в математике обозначают каким-либо знаком: «+», «–», «·», «:». Для логических операций тоже определены свои обозначения. Если операцию отрицания применяют к высказыванию А, то это можно записать так: НЕ А. Можно встретить и другие обозначения для логической операции отрицания: Not A,¬A, Ā, ~A.

Если нас интересует истинность высказывания НЕА, то ее (вне зависимости от содержания) можно определить по таблице истинности:

Из таблицы истинности следует, что отрицанием истинного высказывания будет ложное, а отрицанием ложного — истинное (пример 3.5). Высказывание и его отрицание никогда не могут быть истинными или ложными одновременно.

Отрицанием высказывания «У меня есть компьютер» будет высказывание «У меня нет компьютера» (или высказывание «Неверно, что у меня есть компьютер»). Истинность этих высказываний зависит от конкретного человека. Для одних будет истинным первое высказывание, а для других — второе. Но оба высказывания не могут быть истинными или ложными одновременно для одного и того же человека.

1. 1 Определите, какие из предложений являются высказываниями, а какие нет.
   1. Включи монитор.
   2. Кислород — это газ.
   3. Шишка — это цветок.
   4. Сколько воды утекло?
   5. Все дети — учащиеся.
   6. Хотя бы один пароль будет верным.
2. 2 Определите истинность высказываний.
   1. 123 — это цифра.
   2. Стол — это существительное.
   3. Число 46 является степенью 2.
   4. равно 0,75.
   5. Железо легче воды.
3. 3 Постройте отрицания высказываний.
   1. Миша не может пойти в кино.
   2. Соня любит рисовать.
   3. Все планеты не имеют атмосферы.
   4. В сентябре не бывает дождей.
   5. Солнце светит ярко.
   6. Некоторые птицы улетают на юг.
4. 4 Откройте файл с данными ниже предложениями и отредактируйте их, удалив или вставив частицу «не» так, чтобы все предложения стали истинными высказываниями.
   • Озеро Нарочь не является крупнейшим озером Беларуси.
   • Все горы являются вулканами.
   • Дуб — хвойное дерево.
   • Число 27 является простым числом.
   • Термометр не позволяет определить температуру тела.
   • Число 2016 не делится на 3.
   • Треугольник не является геометрической фигурой.
5. 5 Какие утверждения о животных, представленных на рисунках, истинные, а какие — ложные?
   • Некоторые из этих животных умеют лазать по деревьям.
   • Все животные обитают в лесах.
   • Ни одно из животных не является домашним.
   • Каждое животное можно погладить.
   • Все люди любят мышей.
   • Ни одно из животных не умеет плавать.
6. 6 Откройте файл с рисунком трех цветков. Раскрасьте их так, чтобы каждое из следующих высказываний было истинным.
   • Все цветки имеют желтый круг в середине.
   • На рисунке есть цветок с синими лепестками.
   • На рисунке нет цветка с красными лепестками.
   • Неверно, что цвет круга в середине цветка совпадает с цветом лепестков.
   • Хотя бы у одного цветка лепестки разного цвета.
7. 7 Дополните рисунок из задания 6 изображениями ваз (выберите из файла) так, чтобы каждое из следующих высказываний было ложным.
   1. Все изображения ваз — четырехугольники.
   2. На вазах есть орнамент в виде кругов.
   3. Все круги в орнаменте разного размера.
   4. Хотя бы один круг в орнаменте белого цвета.
8. 8* Решите задачу-стихотворение.

   Собаки с рыжими хвостами

   Себе овсянку варят сами.

   Тем, чьи хвосты стального цвета,

   Не позволяют делать это.

   Кто варит сам себе овсянку,

   Гулять выходит спозаранку.

   Все, кто гулять выходят рано,

   Не терпят фальши и обмана.

   Вид добродушный у Барбоса,

   Но на сорок он смотрит косо.

   Он видит: норовят сороки

   У воробьев списать уроки!

   Скажите — проще нет вопроса! —

   Какого цвета хвост Барбоса?1

Источник: http://informatika7.adu.by/?page_id=104&lang=ru

Построение логического отрицания правило

Отрицание к формуле имеет вид Vx (А(х)—»~|#(х)). Формулируем отрицание:

«Любое целое число, делящееся на 6, нс делится на 4»

. Здесь исходное предложение верно, так как, например число 12 делится и на 6, и на 4.

Отрицание к предложению ложно. • Пример 3.1.9. Построим отрицание к предложению из примера 2.2.2. Предложение «Найдется такое положительное рациональное число а, что все положительные числа, меньшие а, будут иррациональными» имеет символическую запись (3a>,6f€Q) (Vx>0,rправилу 7°: (Va>,aeQ) (ЗдЮДдге!).

Утверждение «Действительное число не является иррациональным» равносильно утверждению «Число рациональное». Поэтому формулу можно переписать так:

Сформулируем отрицание: «Для любого положительного рационального числа а существует положительное число, меньшее а, являющееся рациональным».

Отрицание является истинным высказыванием, так как какое бы положительное рациональное число а мы не взяли, положим, что х=а/2.

Отрицание и двойное отрицание, условия истинности и правила вывода, свойственные отрицанию и двойному отрицанию. Понятие о правилах вывода в логике высказываний

Рассмотрим правило вывода, т.е.

введение, исключение в сложных суждениях.

Общее определение: каждое из правил вывода разрешает из посылки правил записать формулу того вида, что имеет заключение правила.

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

Логические элементы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ и их таблицы истинности

Для всех видов логических элементов, независимо от их физической природы, характерны дискретные значения входных и выходных сигналов.

Логические элементы имеют один или несколько входов и один или два (обычно инверсных друг другу) выхода.

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

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

Традиционно логические элементы выпускаются в виде специальных радиодеталей — интегральных микросхем.

Логические

Отрицание высказываний и высказывательных форм

Если перед всем составным высказыванием поставим слова «неверно, что», то, безусловно, получим его отрицание.

А как быть с частицей «не»? Можно ли ее поставить перед сказуемым составного предложения и получить его отрицание?

Возьмем, например, высказывание «число 28 делится на 9 и на 4».

Оно ложное, так как представляет собой конъюнкцию двух высказываний, одно из которых ложно.

Поставив перед сказуемым этого высказывания частицу «не», получим конъюнкцию «число 28 не делится на 9 и на 4», в которой одно из предложений «число 28 не делится на 4» — ложное и, значит, ложно построенное с помощью частицы «не» предложение.

Поэтому оно не является отрицанием высказывания «число 28 делится на 9 и на 4».

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

Для этого надо убедиться в том, что значения истинности высказываний вида

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

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

Тогда его отрицание «прямой угол не равен девяноста градусам» — ложь.

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

Во всех остальных случаях выражение «А и Б» ложно.

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

Отрицанием высказывания

«некоторые прямоугольные треугольники являются равнобедренными»

и (х)

, также имеющие один и тот же смысл (и одно и то же значение истинности).

Получаем две равносильности:



Формулы и законы логики

Поэтому будем использовать «натуральные» названия.

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

; 2) если

и

– формулы, то формулами также являются выражения вида

. Никаких других формул нет. В частности формулой является любая логическая операция, например логическое умножение

.

Обратите внимание на второй пункт – он позволяет рекурсивным образом «создать» сколь угодно длинную формулу.

Поскольку

–

Умозаключения.

Виды умозаключений

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

В качестве примера рассмотрим рассуждение школьника, которому надо установить отношение «меньше» между числами 7 и 8.

Учащийся говорит: «7 < 8, потому что при счете 7 называют раньше, чем> Выясним, на какие факты опирается вывод, полученный в этом рассуждении.

Таких фактов два: Первый: если число а при счете называют раньше числа b, то a < b. второй: 7 при счете называют раньше, чем> Первое предложение носит общий характер, так как содержит квантор общности – его называют общей посылкой.

Из двух посылок получен новый факт: 7 < 8, его называют> Между

Статья: «Построение математических рассуждений (правило заключения, правило отрицания, правило силлогизма)»

Частная посылка А(а) означает, что а

ТА, а заключение В(а) показывает, что а

ТВ.

Все умозаключение , построенное по правилу заключения, запишется на теоретико-множественном языке так:

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

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

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

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

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

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

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

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

Эти состояния принято обозначать арабскими цифрами один либо ноль или словами true и false. Это возможно из-за того, что для математики важна только истинность высказываний, а конкретное содержание второстепенно. Простые высказывания принято считать логическими переменными, а сложные — функциями логики. Выражения для упрощения записи обозначают латинскими буквами A, B, C.

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

Виды логических операций

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

1. AND (И) — применяется для сравнения двух бит. Результатом действия будет единица, но лишь в том случае, если значения двух ячеек одинаковое. При остальных вариантах итог будет иметь устойчивое нулевое состояние.
2. OR (ИЛИ) — по сути, операция обратная AND. Результат становится нулевым, если содержимое двух сравниваемых бит одинаковое. В остальных случаях он равный единице.
3. XOR (ИЛИ) — если значения, содержащиеся в двух сравниваемых битах противоположны, при выполнении логического действия результат будет равный единице. Во всех остальных случаях он будет равняться нулю.
4. NOT (НЕ) — действие, используемое для одного бита. Если первоначально ячейка находилась в нулевом состоянии, то после выполнения над ней операции она станет равной единице и наоборот. Фактические это логическая инверсия.

Эти операции являются основными элементами при составлении таблиц истинности и получения возможного результата. На основании их построена алгебра Буля.

Некоторые элементы получаются путём объединения нескольких операций. Так, существует состояние: NAND (И-НЕ) и NOR (ИЛИ-НЕ). Первый элемент является инверсией операции «И», а второй — «ИЛИ».

На основании рассмотренных операторов строится работа всех цифровых интегральных схем.

В информатике существует своя терминология, обозначающая то или иное логическое действие. Так, AND называют операцией конъюнкции, OR — дизъюнкции, XOR — сложение по модулю 2, NOT — отрицание. Задача инженера при анализе схем или алгоритма сводится к выполнению булевой арифметики и упрощению выражений. Для этого используют различные правила и положения не требующих доказательства.

Аксиомы и законы

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

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

Поэтому и были сформулированы следующие законы:

1. Торжества. Записывается в виде утверждения: А = А. В этом случае таблица будет состоять из двух комбинаций: ложной и правдивой. Бинарная логическая связка «Если А, то А» является материальной импликацией. Для такого варианта всегда можно сказать, что А есть А. Этот закон обозначает то, что нельзя подменять одно понятие другим, иначе возникнут логические ошибки.
2. Противоречия. Согласно ему, утверждение, что А и НЕ-А, неверно: A & A = 0. Другими словами, если А истинное значение, то его отрицание не может быть ложным. То есть их перемножение будет всегда фальшивой операцией. Этот закон довольно часто применяется для упрощения сложных логических суждений.
3. Третьего исключённого. Закон записывается в виде A v A = 1 и обозначает, что в один и тот же момент высказывание может быть только правдивым или ложным. То есть третьего не дано.

Эти три закона фундаментальны. Без их соблюдения сделать любое правильное утверждение невозможно.

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

В этом случае считается, что функция истинная лишь тогда, когда оба выражения являются верными: F = A & B. Другое логическое сложение (дизъюнкция).

Оно гласит, что если оба выражения ложны, то и логическая функция будет неверной.

Кроме того, используется закон:

• инверсии (отрицания) — если логическое высказывание истинно, то отрицание его будет ложным выражением;
• импликации (следования) — для всегда истинного сложного логического выражения ложь будет тогда, когда из верности следует отрицание;
• эквивалентности (равнозначности) — выражение будет истинным лишь тогда, когда оба высказывания имеют одинаковое значение.

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

Алгоритм построения

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

• подсчитывают количество переменных n;
• вычисляют число строк для будущей таблицы используя формулу m = 2n+1;
• определяют число логических операций;
• устанавливают порядок выполнения операций в соответствии со скобками и приоритетами;
• строят таблицу с указанием столбцов и наборов значений, заданных логических операций;
• заполняют оставшиеся ячейки в таблице.

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

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

Пусть необходимо построить таблицу для логического выражения F = (A → B) * (A + B). Эта формула состоит из двух логических переменных A и B и нескольких операций. Начинают построение с определения строк. Используя формулу 2n+1 для рассматриваемого примера можно установить, что их число будет: x = 22 + 1 = 5.

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

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

1. Импликация в первой скобке.
2. Инверсия во второй скобке переменной A.
3. Отрицание во второй скобке неизвестной B.
4. Сложение во втором члене.
5. Конъюнкция.

В итоге получится, что столбцов будет: Y = 2 + 5 = 7. Теперь нужно построить таблицу 7Х5. В шапку первого и второго столбца вписывают переменные, а затем операции над ними. Затем в строках, соответствующих A и B нужно записать всё, что с ними может произойти. В итоге останется только правильно посчитать последний столбец.

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

Третьей и четвёртой — ноль на один, что в итоге даст ноль. Последний столбец является главным для рассматриваемой логической функции.

По нему можно узнать значение логической функции для любых форм переменных A и B.

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

Например, заданно выражение (x + y + z) * (x + y). По сути, оно записано в совершенно нормальной конъюнктивной форме. Но для приведения его к этому виду нужно, чтобы во втором выражении стояла z.

Для того чтобы её добавить необходимо обратить внимание на то, что внутри скобок стоит логическое сложение. Поэтому дописав к нему ноль, результат не изменится. Добавить ноль через z можно, как ноль умножить на НЕ z.

В итоге получится выражение (x + y + z) * (x + y + z + z), для которого, используя алгоритм составить таблицу уже не так и сложно.

Вычисления онлайн

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

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

Тем более расчёт занимает совсем небольшое количество времени.

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

Из различных порталов можно отметить три наиболее популярных калькулятора:

1. Allcalc.
2. Programforyou.
3. Uchim.

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

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

Онлайн калькулятор позволяет быстро строить таблицу истинности для произвольной булевой функции или её вектора, рассчитывать совершенную дизъюнктивную и совершенную конъюнктивную нормальные формы, находить представление функции в виде полинома Жегалкина, строить карту Карно и классифицировать функцию по классам Поста.

Калькулятор таблицы истинности, СКНФ, СДНФ, полинома Жегалкина

введите функцию или её вектор

Скрыть клавиатуру

∨

∧

¬

⊕

→

≡

↓

↑

0

1

a

b

c

x

y

z

(

)

X1

X2

X3

X4

X5

X6

Показать настройки

Опускать знак конъюнкции

Построить

Построено таблиц, форм: 103523

Как пользоваться калькулятором

1. Введите в поле логическую функцию (например, x1 ∨ x2) или её вектор (например, 10110101)
2. Укажите действия, которые необходимо выполнить с помощью переключателей
3. Укажите, требуется ли вывод решения переключателем «С решением»
4. Нажмите на кнопку «Построить»

В качестве переменных используются буквы латинского и русского алфавитов (большие и маленькие), а также цифры, написанные после буквы (индекс переменной). Таким образом, именами переменных будут: a, x, a1, B, X, X1, Y1, A123 и так далее.

Для записи логических операций можно использоватькак обычные символы клавиатуры (*, +, !, , ->, =), так и символы, устоявшиеся в литературе (∧, ∨, ¬, ⊕, →, ≡).

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

Для смены порядка выполнения операций используются круглые скобки ().

Обозначения логических операций

• И (AND): & • ∧ *
• ИЛИ (OR): ∨ +
• НЕ (NOT): ¬ !
• Исключающее ИЛИ (XOR): ⊕
• Импликация: -> → =>
• Эквивалентность: = ~ ≡
• Штрих Шеффера: ↑ |
• Стрелка Пирса: ↓

Что умеет калькулятор

• Строить таблицу истинности по функции
• Строить таблицу истинности по двоичному вектору
• Строить совершенную конъюнктивную нормальную форму (СКНФ)
• Строить совершенную дизъюнктивную нормальную форму (СДНФ)
• Строить полином Жегалкина (методами Паскаля, треугольника, неопределённых коэффициентов)
• Определять принадлежность функции к каждому из пяти классов Поста
• Строить карту Карно
• Минимизировать ДНФ и КНФ
• Искать фиктивные переменные

Что такое булева функция

Булева функция f(x1, x2, … xn) — это любая функция от n переменных x1, x2, … xn, в которой её аргументы принимают одно из двух значений: либо 0, либо 1, и сама функция принимает значения 0 или 1. То есть это правило, по которому произвольному набору нулей и единиц ставится в соответствие значение 0 или 1. Подробнее про булевы функции можно посмотреть на Википедии.

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

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

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

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

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

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

Логическая операция — операция над высказываниями, позволяющая составлять новые высказывания путём соединения более простых. В качестве основных операций обычно называют конъюнкцию (∧ или &), дизъюнкцию (∨ или |), импликацию (→), отрицание (¬), эквивалентность (=), исключающее ИЛИ (⊕).

Как задать логическую функцию

Есть множество способов задать булеву функцию:

• таблица истинности
• характеристические множества
• вектор значений
• матрица Грея
• формулы

Рассмотрим некоторые из них:

Чтобы задать функцию через вектор значений необходимо записать вектор из 2n нулей и единиц, где n — число аргументов, от которых зависит функция. Например, функцию двух аргументов можно задать так: 0001 (операция И), 0111 (операция ИЛИ).

Чтобы задать функцию в виде формулы, необходимо записать математическое выражение, состоящее из аргументов функции и логических операций. Например, можно задать такую функцию: a∧b ∨ b∧c ∨ a∧c

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

• Совершенная дизъюнктивная нормальная форма (СДНФ)
• Совершенная конъюнктивная нормальная форма (СКНФ)
• Алгебраическая нормальная форма (АНФ, полином Жегалкина)

Совершенная дизъюнктивная нормальная форма (ДНФ)

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

Дизъюнктивная нормальная форма (ДНФ) — это дизъюнкция простых конъюнкций.

Совершенная дизъюнктивная нормальная форма (СДНФ) — ДНФ относительно некоторого заданного конечного набора переменных, в каждую конъюнкцию которой входят все переменные данного набора.

Например, ДНФ является функция ¬abc ∨ ¬a¬bc ∨ ac, но не является СДНФ, так как в последней конъюнкции отсутствует переменная b.

Совершенная конъюнктивная нормальная форма (КНФ)

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

Конъюнктивная нормальная форма (КНФ) — это конъюнкция простых дизъюнкций.

Совершенная конъюнктивная нормальная форма (СКНФ) — КНФ относительно некоторого заданного конечного набора переменных, в каждую дизъюнкцию которой входят все переменные данного набора.

Например, КНФ является функция (a ∨ b) ∧ (a ∨ b ∨ c), но не является СДНФ, так как в первой дизъюнкции отсутствует переменная с.

Алгебраическая нормальная форма (АНФ, полином Жегалкина)

Алгебраическая нормальная форма, полином Жегалкина — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции, а в качестве сложения — исключающее ИЛИ.

Примеры полиномов Жегалкина: 1, a, a⊕b, ab⊕a⊕b⊕1

Алгоритм построения СДНФ для булевой функции

1. Построить таблицу истинности для функции
2. Найти все наборы аргументов, на которых функция принимает значение 1
3. Выписать простые конъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 0, то она входит в конъюнкцию с отрицанием, а иначе без отрицания
4. Объединить все простые конъюнкции с помощью дизъюнкции

Алгоритм построения СКНФ для булевой функции

1. Построить таблицу истинности для функции
2. Найти все наборы аргументов, на которых функция принимает значение 0
3. Выписать простые дизъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 1, то она входит в дизъюнкцию с отрицанием, а иначе без отрицания
4. Объединить все простые дизъюнкции с помощью конъюнкции

Алгоритм построения полинома Жегалкина булевой функции

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

1. Построить таблицу истинности для функции
2. Добавить новый столбец к таблице истинности и записать в 1, 3, 5… ячейки значения из тех же строк предыдущего столбца таблицы истинности, а к значениям в строках 2, 4, 6… прибавить по модулю два значения из соответственно 1, 3, 5… строк.
3. Добавить новый столбец к таблице истинности и переписать в новый столбец значения 1, 2, 5, 6, 9, 10… строк, а к 3, 4, 7, 8, 11, 12… строкам аналогично предыдущему пункту прибавить переписанные значения.
4. Повторить действия каждый раз увеличивая в два раза количество переносимых и складываемых элементов до тех пор, пока длина не станет равна числу строк таблицы.
5. Выписать булевы наборы, на которых значение последнего столбца равно единице
6. Записать вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора записать единицу) и объединить их с помощью операции исключающего ИЛИ.

Построим совершенные дизъюнктивную и дизъюнктивную нормальные формы, а также полином Жегалкина для функции трёх переменных F = ¬ab∨¬bc∨ca

1. Построим таблицу истинности для функции

Построение совершенной дизъюнктивной нормальной формы:

Найдём наборы, на которых функция принимает истинное значение: { 0, 0, 1 } { 0, 1, 0 } { 0, 1, 1 } { 1, 0, 1 } { 1, 1, 1 }

В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием:

K1: { 0, 0, 1 } — ¬a¬bc
K2: { 0, 1, 0 } — ¬ab¬c
K3: { 0, 1, 1 } — ¬abc
K4: { 1, 0, 1 } — a¬bc
K5: { 1, 1, 1 } — abc

Найдём наборы, на которых функция принимает ложное значение: { 0, 0, 0 } { 1, 0, 0 } { 1, 1, 0 }

В соответствие найденным наборам поставим элементарные дизъюнкции по всем переменным, причём если переменная в наборе принимает значение 1, то она будет записана с отрицанием:

D1: { 0, 0, 0 } — a∨b∨c
D2: { 1, 0, 0 } — ¬a∨b∨c
D3: { 1, 1, 0 } — ¬a∨¬b∨c

Объединим дизъюнкции с помощью конъюнкции и получим совершенную конъюнктивную нормальную форму:

D1 ∧ D2 ∧ D3 = (a∨b∨c) ∧ (¬a∨b∨c) ∧ (¬a∨¬b∨c)

Добавим новый столбец к таблице истинности и запишем в 1, 3, 5 и 7 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 2, 4, 6 и 8 сложим по модулю два со значениями из соответственно 1, 3, 5 и 7 строк:

Добавим новый столбец к таблице истинности и запишем в 1 и 2, 5 и 6 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 3 и 4, 7 и 8 сложим по модулю два со значениями из соответственно 1 и 2, 5 и 6 строк:

Добавим новый столбец к таблице истинности и запишем в 1 2, 3 и 4 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 5, 6, 7 и 8 сложим по модулю два со значениями из соответственно 1, 2, 3 и 4 строк:

Окончательно получим такую таблицу:

Выпишем наборы, на которых получившийся вектор принимает единичное значение и запишем вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора следует записать единицу):

{ 0, 0, 1 } — c, { 0, 1, 0 } — b, { 0, 1, 1 } — bc, { 1, 1, 0 } — ab, { 1, 1, 1 } — abc