26 элементарные логические операции алгебры логики

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

Основное понятие
булевой алгебры — выказывание.
Под простым высказыванием понимается
повествовательное предложение, о котором
можно сказать, истинно оно или ложно
(третьего не дано). Высказывания
обозначаются латинскими буквами и могут
принимать одно из двух значений: ЛОЖЬ
(обозначим 0) или ИСТИНА (обозначим 1).
Например, содержание высказывания А:
«дважды два равно четырем» истинно А =
1, а высказывание В: «три больше пяти»
всегда есть ЛОЖЬ.

Два высказывания А
и В называются равносильными,
если они имеют одинаковые значения
истинности, записывается А = В.

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

Операцией отрицания
А называют высказывание

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

Это правило можно
записать в виде следующей таблицы:

А

0

1

1

0

Такая таблица
называется таблицей
истинности
.

Конъюнкцией
(логическим умножением) двух высказываний
А и В является новое высказывание С,
которое истинно только тогда, когда
истинны оба высказывания, записывается
С = А 
В или С = А & В (при этом говорят «С равно
А и В»). Примером такой операции может
быть следующая: пусть высказывание А
состоит в том, что «высота шкафа меньше
высоты двери», событие В «ширина шкафа
меньше ширины двери», событие С «шкаф
можно внести в дверь, сели ширина шкафа
меньше ширины двери И высота шкафа
меньше высоты двери», т.е. данная операция
применяется, если два высказывания
связываются союзом И.

Таблица истинности
этой операции, как следует из определения,
имеет вид

А

В

А & В

0

0

0

0

1

0

1

0

0

1

1

1

Дизъюнкцией
(логическим сложением) двух высказываний
А и В является новое высказывание С,
которое истинно, если истинно хотя бы
одно высказывание. Записывается С = A

В (при этом говорят: «С равно А ИЛИ В).
Пример такой операции следующий: пусть
высказывание А состоит в том, что «студент
может добираться домой на автобусе»,
событие В «студент может добираться
домой на троллейбусе», событие С «студент
добрался домой на автобусе ИЛИ
троллейбусе», т.е. данная операция
применятся, если два высказывания
связываются союзом ИЛИ.

Таблица истинности
такой операции следующая:

А

В

A

В

0

0

0

0

1

1

1

0

1

1

1

1

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

Таблица истинности
импликации следующая:

А

В

А 
В

0

0

1

0

1

1

1

0

0

1

1

1

Импликация имеет
следующие свойства:

А 
В ≠ В 
А

А 
А = 1

0 
А = 1

1 
А = А

А 
1 = 1

А 
0 =

Эквиваленцией двух
высказываний А и В является новое
высказывание С, которое истинно только
тогда, когда оба высказывания имеют
одинаковые значения истинности,
записывается С = А 
В (.С = А 
В). Примером такой операции может быть
любое высказывание типа: событие А
равносильно событию В.

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

А

В

А 
В

0

0

1

0

1

0

1

0

0

1

1

1

Эквиваленция имеет
следующие свойства:

А 
В = В 
А

А 
В =

А 
1 = А

А 
0 =

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

В) 
В) 
А.

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

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

Одну и ту же зависимость
между логическими переменными можно
выразить различными формулами. Поэтому
важно иметь возможность приводить
формулы с помощью эквивалентных
преобразований к некоторому стандартному
виду. Существует несколько стандартных
форм, к которым приводятся логические
выражения с помощью эквивалентных
преобразований (формулы 1 — 23).

Первая из них –
дизъюнктивная
нормальная форма (ДНФ)
,
имеет вид

A1

А2


А
n,

где каждое из
составляющих высказываний есть конъюнкция
простых высказываний и их отрицаний,
например: В = (

& А2 & A3) 
(А4 & А5).

Вторая – конъюнктивная
нормальная форма (КНФ), имеет вид

A1

А2


А
n,

где каждое из
составляющих есть дизъюнкция Гфостых
высказываний и их отрицаний, например:
В = (


А2 

)
& (А4 
А5) & А6.

Задать булевскую
функцию можно, определяя ее значения
для всех наборов значений аргументов.
Каждый аргумент может иметь два значения:
0 и 1, следовательно, n
аргументов могут принимать 2n
различных наборов. Пусть, например,
булевская функция имеет три аргумента:
Х1, X2,
Х3. Общее число наборов 23
= 8. Зададим таблицу истинности функции,
указав для каждого набора значение
функции.

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

&
&X3),
все элементы соединяются знаками
дизъюнкции.

Для рассматриваемого
примера получим

F(X1,
Х2, X3)
= (
&
&X3)(
&
Х2 & X3)(Х1
&
&X3)
(Х1&Х2&X3).

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

Аналогично, для
комбинаций, где функция принимает
значение нуля, можно построить
алгебраическую форму

F(X1,
Х2, X3)
= (Х1Х2X3)
& (Х1
X3)
& (
Х2X3)
& (

X3),

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #

Алгебра логики

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

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

Алгебра логики является частью дискретной математики – раздела математики, изучающего свойства структур конечного характера.

Сама алгебра логики изучает свойства функций, у которых значения как аргументов, так и самих функций ограничены двумя значениями, например, ({0,1}).

Отцом алгебры логики считается английский математик Джордж Буль (1815-1864), поэтому алгебру логики иногда называют булевой алгеброй.

Долгое время алгебра логики была известна лишь узкому кругу специалистов, и только в 1938 году американский математик Клод Шеннон (1916-2001), стоявший у истоков современной информатики, показал, что алгебра логики применима для описания самых разных процессов, в том числе релейных и транзисторных схем.

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

Так, примерами высказываний могут служить такие фразы, как “сегодня идет дождь”, или “завтра я не пойду в институт”.

Определение истинности высказывания не всегда тривиально. Так, например:

Великая теорема Ферма

Для любого натурального числа (n>2) уравнение [ a^n + b^n = c^n] Не имеет решений в целых ненулевых числах (a,,b,,c)

Как известно, сформулированная Пьером Ферма в 1637 году, была окончательно доказана только в 1994.

Введем не совсем формальное, но достаточное для наших целей определение

Высказывание
это языковое образование, в отношении которого имеет смысл говорить о его истинности или ложности.

Это определение было предложено Аристотелем.

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

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

Следует заметить, что высказыванием в строгом смысле является только утверждение о конкретных объектах. Если речь идет о неких переменных, например, “x – рациональное число”, то мы говорим о неких функциях, имеющих значение “истина” или “ложь”. Такие функции называются предикатами.

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

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

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

Различные языковые связки, такие, как “не”, “если …, то …”, “или”, “и”, и т.п. позволяют строить из элементарных высказываний более сложные.

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

Введем некоторые из них.

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

Конъюнкция обозначается различными способами, в частности, амперсандом (a ,&,b), точкой (a cdot b), или “крышкой” (a wedge b), и соответствует языковой связке “и”. Мы будем в основном использовать амперсанд.

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

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

Дизъюнкция соответствует союзу “или”, и обозначается плюсом (a+b), или “галочкой” (avee b). Мы будем использовать в основном второй вариант.

Таблица истинности дизъюнкции, по определению:

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

Строгая дизъюнкция соответствует связке “либо …, либо …”, и обозначается плюсом в кружочке (aoplus b), или треугольником (avartriangle b). Будем в основном пользоваться первым обозначением.

Таблица истинности, по определению:

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

Импликация соответствует связке “если …, то …”, и обозначается стрелкой (a rightarrow b), или (a Rightarrow b)

Таблица истинности, по определению:

(p) (q) (prightarrow q)
0 0 1
0 1 1
1 0 0
1 1 1

Импликация, на первый взгляд, имеет не очевидное определение: как вдруг из ложных условий получается истинное следствие. Однако, в математике это никакая не новость. Например, возьмем очевидно ложное утверждение “один равен двум”:

[1 = 2] [2 = 1]

Складывая эти равенства, получим очевидно истинный результат:

[3=3.]

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

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

Эквивалентность соответствует связке “тогда и только тогда, когда”, и обозначается (a Leftrightarrow b), или (a equiv b), или (a sim b), или (a leftrightarrow b). Будем в основном пользоваться первыми двумя обозначениями.

Таблица истинности, по определению:

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

Инверсия соответствует связке “не”, и обозначается (neg a), или (;overline{a};), или (!a). Будем в основном пользоваться первыми двумя обозначениями.

Таблица истинности, по определению:

(p) (;overline{p};)
0 1
1 0

В заключение, таблица истинности основных логических операций:

(p) (q) (;overline{p};) (p,&,q) (pvee q) (poplus q) (prightarrow q) (pequiv q)
0 0 1 0 0 0 1 1
0 1 1 0 1 1 1 0
1 0 0 0 1 1 0 0
1 1 0 1 1 0 1 1

Законы алгебры логики

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

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

Существуют следующие “законы” алгебры логики, определяющие некий набор эквивалентных формул:

Законы коммутативности
[x ,&,y = y ,&,x] [x vee y = yvee x]
Законы ассоциативности
[ (x ,&,y) ,&,z = x ,&,(y ,&,z)] [ (x vee y) vee z = x vee(y vee z)]
Законы поглощения
[xvee 0 = x] [x,&,1 = x]
Законы дистрибутивности
[ x,&,(yvee z) = (x,&,y) vee(x,&,z)] [ xvee(y,&,z) = (x vee y) ,&,(xvee z)]
Закон противоречия
[ x ,&,;overline{x}; = 0]
Закон исключения третьего
[ x vee;overline{x}; = 1]
Закон равносильности
[ x ,&,x = x] [ x vee x = x ]
Закон двойного отрицания
[;overline{;overline{x};}; = x ]
Законы де Моргана
[ ;overline{x,&,y}; = ;overline{x}; vee;overline{y}; ] [ ;overline{xvee y}; = ;overline{x}; ,&,;overline{y}; ]
Законы поглощения
[ xvee(x,&,y) = x] [ x,&,(xvee y) = x]

Все перечисленные законы элементарно доказываются составлением таблиц истинности.

Например, первый закон де Моргана:

(x) (y) (x,&,y) (;overline{x,&,y};) (;overline{x};) (;overline{y};) (;overline{x}; vee;overline{y};)
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0

3 и 6 столбец одинаковы, следовательно, соответствующие формулы эквивалентны.

Введем еще одно определение

Тавтология
логическая формула, которая всегда истинна.

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

Формальное решение логических задач

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

Итак, формальный способ решения логических задач:

  1. Из условий задачи выделяются простые высказывания и обозначаются как логические переменные.
  2. Условия задачи записываются в виде логических формул
  3. Составляется единое логическое выражение, соответствующее условию задачи. По условию задачи оно является истинным.
  4. Полученное выражение упрощается, либо составляется таблица истинности для него (либо и то, и другое)
  5. Выбирается решение задачи (случаи, когда условие истинно)
  6. Решение формулируется в исходных терминах задачи.

Пример: (источник)

На весеннем фестивале, четыре садовника показывали выращенные ими розы.

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

Известно, что

  • У первого была желтая роза
  • У второго не было красной розы
  • У третьего была синяя роза, но не было зеленой
  • У одного из садовников с зеленой розой не было красной
  • Ни у одного из садовников с желтой розой не было зеленой
  • Ни у кого нет роз двух одинаковых цветов

Введем переменные, в которых название переменной соответствует цвету, а индекс – садовнику (номеру). Это автоматически учитывает условие “Ни у кого нет роз двух одинаковых цветов”. Тогда условия задачи запишутся в виде:

  • (y_1)
  • (;overline{r_2};)
  • (b_3 ,&,;overline{g_3};)
  • ((g_1rightarrow;overline{r_1};) oplus(g_2rightarrow;overline{r_2};)oplus(g_3rightarrow;overline{r_3};)oplus(g_4rightarrow;overline{r_4};))
  • ((y_1rightarrow;overline{g_1};) ,&,(y_2rightarrow;overline{g_2};),&,(y_3rightarrow;overline{g_3};),&,(y_4rightarrow;overline{g_4};))

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

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

Рассматривая последнее условие:

((y_1rightarrow;overline{g_1};) (y_2rightarrow;overline{g_2};)(y_3rightarrow;overline{g_3};)(y_4rightarrow;overline{g_4};))

Первая импликация истинна, только если (;overline{g_1};) истинно. Предпоследняя импликация истинна всегда, (;overline{g_3};). Можем переписать в виде:

(y_1 ;overline{g_1}; (y_2rightarrow;overline{g_2};) (y_4rightarrow;overline{g_4};))

Рассмотрим предпоследнее условие

[
(g_1 rightarrow;overline{r_1};)
oplus(g_2 rightarrow;overline{r_2};)
oplus(g_3 rightarrow;overline{r_3};)
oplus(g_4 rightarrow;overline{r_4};)
]

Первая импликация всегда истинна, поскольку (;overline{g_1};), вторая всегда истинна, поскольку (;overline{r_2};), третья всегда истинна, поскольку (;overline{g_3};). Получаем:

[
1
oplus 1
oplus 1
oplus(g_4 rightarrow;overline{r_4};)
]

[
1 oplus(g_4 rightarrow;overline{r_4};)
]

Легко показать, что (1 oplus x = ;overline{x};). Тогда условие принимает вид

[
;overline{g_4 rightarrow;overline{r_4};};
]

Импликацию можно представить в виде (x rightarrow y = ;overline{x}; vee y)

Применяя закон де Моргана,

[
r_4 g_4
]

Записывая все условия вместе:

[
y_1 ;overline{g_1};
;overline{r_2};
(;overline{y_2}; vee;overline{g_2};)
(;overline{y_4}; vee;overline{g_4};)
b_3 ;overline{g_3};
g_4 r_4
]

Учитывая (g_4 (;overline{y_4}; vee;overline{g_4};) = g_4 ;overline{y_4};),

[
y_1 ;overline{g_1};
;overline{r_2};
(;overline{y_2}; vee;overline{g_2};)
b_3 ;overline{g_3};
;overline{y_4};
g_4 r_4
]

Известно, что зеленые розы должны быть у двух садовников:

[
;overline{g_1}; ;overline{g_2}; g_3 g_4
vee;overline{g_1}; g_2 ;overline{g_3}; g_4
vee;overline{g_1}; g_2 g_3 ;overline{g_4};
vee g_1 ;overline{g_2}; ;overline{g_3}; g_4
vee g_1 ;overline{g_2}; g_3 ;overline{g_4};
vee g_1 g_2 ;overline{g_3}; ;overline{g_4};
]

А так как (;overline{g_3};) и (;overline{g_1};)

[
;overline{g_1}; g_2 ;overline{g_3}; g_4
]

Получаем (g_2), тогда (g_2 (;overline{y_2}; vee;overline{g_2};) = g_2 ;overline{y_2};)

Аналогично для желтых:

[
y_1 ;overline{y_2}; y_3 ;overline{y_4};
]

Получаем (y_3). Поскольку (y_3 b_3), можно утверждать (;overline{r_3}; ;overline{g_3};)

Для красных тогда:

[
r_1 ;overline{r_2}; ;overline{r_3}; r_4
]

Получаем (r_1). Поскольку (r_1 y_1), можем утверждать (;overline{b_1}; ;overline{g_1};)

Для синих:

[
;overline{b_1}; b_2 b_3 ;overline{b_4};
]

Получаем (b_2).

Итого

[
y_1 r_1
g_2 b_2
b_3 y_3
g_4 r_4
]


  1. Вообще сейчас считается, что у пространства, в котором мы находимся, времеподобная метрика Миньковского.↩︎

План урока:

Алгебра логики и решение задач

Основные операции

Сравнение операций, первоочередность

Диаграммы Эйлера-Венна

Законы алгебры логики

Электросхемы и таблицы истинности

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

  • Способ рассуждений.
  • Табличный способ.
  • Решение при помощи средств логики.

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

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

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

Алгебра логики и решение задач

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

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

Стоит остановиться на базовых понятиях алгебры логики:

  • константы (0,1);
  • переменные;
  • формула;
  • знаки операций;
  • скобки.

Логическая переменная – обозначение логического выражения, которое может быть true (t, правда, истина, да, 1) – false (f, ложь, нет, 0).

Формула– символьный способ выражения операции между переменными при помощи специальных знаков и скобок ().

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

Образец таких предложений: «Луна – вертится вокруг Марса» – ложно, а «После зимы всегда приходит весна» – истинно.

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

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

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

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

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

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

Еще используют понятие «предикат» – содержит любое количество переменных без перечисления всех составляющих данных. Это предикат простых, отрицательных P(x)=(x<0) чисел.

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

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

Основные операции

Количество логических операций, которыми обычно оперирует логика 6:

  • Отрицание.
  • Умножение.
  • Сложение
  • Следование.
  • Дизъюнкция.
  • Равнозначность.

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

Отрицание или инверсия

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

На примере этой простейшей операции удобно показывать, насколько лаконичны и информативны таблицы истинности. Обозначим исходное высказывание буквой А, соответственно, окончательное будет не А (или НЕ, ‾, ˥ not А). А их ложность или правдивость напишем при помощи цифр 0 и 1.

1 logicheskie operacii

Получается, если исходное значение правда, то новое будет ложь, и наоборот.

Умножение или конъюнкция &

Логическое И или умножение еще называют конъюнкцией. Финальное высказывание будет правдивым, только если его составляющие тоже правдивы. Во всех остальных случаях оно будет ложным. Применяется для двух и более аргументов, элементарных или сложных. Обозначение А и В; А ^ В; А &В; A and В.

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

2 logicheskie operacii

Логическое И в обычной жизни:

  • Хорошая певица должна быть талантливой и упорной (наличие только одного качества не позволит проявить миру свой талант).
  • По условиям задачи А – число меньше 30, В – число делиться на 3. Нужно найти решение А ˄ В.

Решение: Первое множество содержит числа 1,2,3….29. Второе – 3,6,9,…27. Решением будет множество на пересечении множеств А и В, что хорошо покажут диаграммы Эйлера-Венна. А ˄ В будет истинным для множества чисел 3,6,9,….27.

Сложение или дизъюнкция V

Логическое ИЛИ, сложение по-другому называют дизъюнкцией. Оно истинно всегда, кроме случая, если ложны все составные высказывания. Функция распространяется на простые и сложные исходные аргументы. Обозначение А или В; A v В; А ог В.

3 logicheskie operacii

В обычной жизни нас окружает логическое ИЛИ:

  • «Чтобы сдать тесты на «отлично», нужно старательно готовиться ИЛИ должно повезти с билетом».
  • Есть задача с 2-мя условиями: А – число делится на 5, В – число делится на 2.

Решение: Первое множество чисел включает в себя 5, 10, 15…Второе – 10, 20, 30…Решение, при котором истинно Аv В – совокупность обеих множеств (5, 10, 15, 20, 25, 30…).

Следование или импликация

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

4 logicheskie operacii

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

5 logicheskie operacii

Логическое следование в обычной жизни:

  • Если пойти к врачу, можно выздороветь (но можно выздороветь и без похода к врачу, а можно и после визита в больницу не выздороветь).
  • По условию задачи, А – если число делится на 10, то В делится на 5.

Строгая дизъюнкция

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

6 logicheskie operacii

Это пример исключающей функции. Аналог в словесном выражении – «либо». Разница от простой дизъюнкции в том, что конечное выражение будет истинным, только если будет правдой одна переменная.

7 logicheskie operacii

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

Операция, выдающая истину в случае, если обе исходные переменные истины или неправдивы.Обозначают А ~В, А В.

8 logicheskie operacii

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

9 logicheskie operacii

Пример эквивалентности из обычной жизни:

  • Если вечером на горизонте солнце темно-красного цвета, значит, завтра будет ветреный день.
  • В задаче 2 условия: А – сумма цифр числа равно 9, В – число делится на 9. АВ означает, что число делится на 9, если сумма цифр равна 9.

Сравнение операций, первоочередность

Приведены результаты основных логических функций для 2-х переменных:

10 logicheskie operacii

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

11 logicheskie operacii

Но скобки делают операцию внутри них самой приоритетной.

Законы алгебры логики

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

Таблица законов алгебры логики

12 logicheskie operacii

Диаграммы Эйлера-Венна

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

Число пересечений (областей) можно посчитать сразу, оно равно n = 2N, где N – число множеств. Так как значение двойки в степени растет очень быстро (4,8,16), обычно диаграммы используют для 2-3 множеств. Далее области пересечения будут сливаться, образуя неразличимые участки. Если множеств 2-3, то рисуют круги, если больше 4 – эллипсы. Этот «цветок» помещают в прямоугольную конструкцию, которую называют универсум U (универсальное множество).

13 logicheskie operacii
Источник

14 logicheskie operacii
Источник

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

Конъюнкция множеств А и В:

15 logicheskie operacii

Отрицание Ā:

16 logicheskie operacii

Сложное выражение (Ā)∨(A∧B), составленное из элементарных Ā, A∧B и их комбинации, графическое выражение:

17 logicheskie operacii

Примеры использования диаграмм Эйлера-Венна

Пример №1:

Есть 2 множества цифр и универсум:

А={4,5,6,7}

В={6,7,8,9}

U={0,4,5,6,7,8,9}

 Пустой области ничего не принадлежит, опишем в табличном виде, какие цифры какой области принадлежит:

18 logicheskie operacii

Электросхемы и таблицы истинности

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

19 logicheskie operacii

Переменными являются переключатели, а результат (горит лампа/идет ток) будет «1» – истина или «0» – ложь.

Для конъюнкции и инверсии подходит последовательное соединение, но во втором случае переключатель один, для дизъюнкции – параллельное.

20 logicheskie operacii

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

21 logicheskie operacii

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

Что такое алгебра и алгебра логики

Алгебра — это раздел математики, который обобщенно можно охарактеризовать, как расширение и обобщение арифметики.

Алгебра логики

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

Законы алгебры логики

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

Законы алгебры логики

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

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

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

Закон двойственности и инверсии (закон Моргана) — основоположником данного правила стал шотландский математик и логик де Морган. Он разработал правило, которое связывает логические операции конъюкцию (И) и дизъюнкцию (ИЛИ) с помощью отрицания.

Основные законы алгебры логики представлены в таблице:

Законы алгебры логики

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

В информатике предоставляется два вида высказываний: простое и сложное. 

Элементы алгебры логики

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

Примеры:

  • Нью-Йорк — столица США (ложное);

  • в России 1117 городов (верное).

Алгебра логики

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

Пример:

Идёт дождь, а у меня нет зонта.

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

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

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

Данная операция используется при обозначении отрицания. Она обозначается знаками — NO, NOT, ! В=2 (истина), а после выполнения операции отрицания, В, к примеру, приобретет значение 1 (ложное).

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

101

Результаты операции НЕ следующие:

  • если исходное выражение истинно, то результат его отрицания будет ложным;

  • если исходное выражение ложно, то результат его отрицания будет истинным. 

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

Понятие «Логическое ИЛИ» также можно заменить понятием «Дизъюнкция». Данная операция обозначается знаками — ИЛИ, OR, ||, |. 

Но есть небольшое отличие: в «Логическом И» результат отрицания равен единице, если оба обозначения равны единице, а в «Логическом ИЛИ» итог равен единице, если одно из обозначений равно единице.

Таблица истинности операции ИЛИ:

102

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

В истории данная операция также обозначается как логическое умножение и конъюнкция. Данная операция обозначается элементами — И, AND, &&, &.

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

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

Таблица истинности операции И приведена ниже:

103

Логическое следование (импликация) — ЕСЛИ ТО

Данная программа имеет также название «Импликация». Она образуется из двух высказываний, которые соединяет: «если…, то».

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

Таблица истинности операции ЕСЛИ ТО выглядит так:

104

Операция эквивалентности (равнозначности) — А ТОГДА И ТОЛЬКО ТОГДА, КОГДА В

Данная операция определяется так: сложное высказывание будет истинно тогда и только тогда, когда и А, и В — истинные.

И наоборот: сложное высказывание будет ложным тогда и только тогда, когда и А, и В — ложные.

Таблица истинности операции эквивалентности:

105

>

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *