Диаграммы эйлера-венна

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

Умножение (конъюнкция)

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

Обозначается таким образом: F = A & B.

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

A	B	F
1	1	1
1
1

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

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

Записывается так: F = A + B.

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

A	B	F
1	1	1
1	1
1	1

Отрицание (инверсия)

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

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

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

A	неА
1
1

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

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

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

A	B	F
1	1	1
1
1	1
1

Равнозначность (эквивалентность)

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

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

A	B	F
1	1	1
1
1
1

Примечание: Операции в сложном логическом выражении выполняются в следующем порядке:

• Инверсия
• Конъюнкция
• Дизъюнкция
• Импликация
• Эквивалентность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как логические операторы работают с целыми числами

Мы уже знаем, что логические операции применимы к логическим аргументам (операндам). Каждый логический операнд — это выражение, которое является истинным (true) или ложным (false) — то есть возвращает булево значение. Иными словами, логический операнд — это выражение типа boolean.

Выходит, применять логические операторы к целочисленным аргументам нельзя?

Можно. Внутри Java все целочисленные типы представлены двоичными числами разной длины. И к ним уже применимы бинарные логические операторы ^, | и &.

Только в этом случае они работают с двоичным представлением операндов — выполняют операции над их битами попарно (рассматривая их как логические единицы и нули). Поэтому и сами операторы ^, | и & зовутся побитовыми.

Как ^, | и & работают с целочисленными операндами

Рассмотрим пример:

Чтобы повторить вычисления Java, нужно:

• Перевести значения обоих операндов в двоичную систему счисления.
• Расположить результаты перевода друг под другом.
• Сравнять в них число разрядов (дополнить лидирующими нулями).
• Применить к битам из каждого столбца оператор (&, | или ^).
• Записать результат каждой операции ниже в том же столбце.
• Перевести итог в десятичную форму.

Потренируемся: вычислим сами 3 & 5

Число 3 в двоичной системе счисления имеет вид 11, а число 5 — 101.

Так как у числа 5 три разряда в двоичной системе, а у числа 3 — всего два, добавим лидирующий ноль к числу 3 в двоичной системе и получим 011.

Берём цифры из обоих чисел и применяем к ним попарно оператор & (AND):

3(10) = 011(2)	1	1
	&	&	&
5(10) = 101(2)	1	1
	=	=	=
001(2) = 1(10)	1

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

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

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

В этой таблице содержатся все возможные наборы переменных. Количество наборов N зависит от количества различных переменных i как N = 2i.

Чтобы удобно записать наборы, нумеруем их по порядку начиная с 0, переводим их номер в двоичную систему счисления (2сс) и записываем набор цифр.

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

инверсия берет только 1 переменную и сразу меняет ее значение:

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

дизъюнкция вернет 1, если хотя бы одна из переменных равна 1:

эквиваленция вернет 1, если переменные равны, и 0 в противном случае:

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

Импликацию можно выразить через дизъюнкцию:А ⇒ В = ¬А ∨ В

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

Например, для выражения: А ∧ (В ∨ С) ≡ В ⇒ ¬А.

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

Здесь порядок операций будет следующим:

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

Чтобы удобно записать наборы, пронумеруем их по порядку начиная с 0. Переведем их номер в 2сс и запишем набор цифр. У нас 3 различные переменные, поэтому должно быть 8 наборов.

1. Первое действие — сложение В и С. Для каждого набора запишем результат сложения в соответствующий столбец.

2. Второе действие — инверсия переменной А.

3. Третье действие — умножение значения А на результат первого действия:

4. Четвертое — импликация значения В и результата второго действия:

5. И последнее действие — эквиваленция результатов 3 и 4 действий:

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

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

В алгебре логики имеется шесть логических операций.

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

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

А	¬ А
1
1

Высказывание истинно тогда и только тогда, когда истинны оба исходных высказывания.

A	B	A ∧ B
1
1
1	1	1

Высказывание ложно тогда и только тогда, когда ложны оба исходных высказывания.

A	B	A ∨ B
1	1
1	1
1	1	1

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

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

A	B	A → B
1
1	1
1
1	1	1

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

Строгая дизъюнкция (Исключающее ИЛИ)

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

A	B	A ⊕ B
1	1
1	1
1	1

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

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

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

A	B	A B
1
1
1
1	1	1

В разговорной речи эквивалентности соответствует связка «тогда и только тогда, когда», а в математике — «необходимо и достаточно».

Эквивалентность — это обратная операция для операции «исключающее ИЛИ», т. е. A B = A ⊕ B

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

Операция	Обозначение	Речевой оборот
Отрицание, инверсия, (лог. НЕ)	¬A, A, not A, не A	«Не», «не верно, что»
Конъюнкция (лог. умножение, лог. И)	A ∧ B, A&B, A · B, AB, A и B, A and B	«И», «как …, так и», «вместе с», «но», «хотя»
Дизъюнкция (лог. сложение, лог. ИЛИ)	A ∨ B, A + B, A | B, A ИЛИ B, A or B	«Или», «или …, или …,или оба вместе»
Строгая дизъюнкция (искл. дизъюнкция, искл. ИЛИ)	A ⊕ B, A xor B	«Либо …, либо», «только … или только»
Импликация (лог. следование)	A → B, A ⇒ B	«Если …, то», «из …следует», «влечёт»
Эквиваленция (эквивалентность, равнозначность)	A B, A ⇔ B,A ≡ B	«Эквивалентно», «необходимо и достаточно»

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

Для логического выражения справедливо:

• всякая логическая переменная, а также логические константы (0, 1), есть логическое выражение;
• если A — логическое выражение, то и A — логическое выражение;
• если A и B — выражения, то связанные любой бинарной операцией они также представляют собой логическое выражение.

При преобразовании или вычислении значения логического выражения логические операции выполняются в соответствии с их приоритетом:

1. отрицание;
2. конъюнкция;
3. дизъюнкция, строгая дизъюнкция;
4. импликация, эквиваленция.

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

9.2 Элементы теории множеств

9.2.1 Множество

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

Множества обозначают заглавными латинскими буквами (например, \(A\)), а его элемента прописными латинскими буквами (например, \(a_1\), \(a_2\) и т.д.).

Множества удобно изображать кружочками. Примерно так:

Если элемент входит в данное множество, то мы говорим, что этот элемент принадлежит данному множеству, и записываем это следующим образом:

\

Символ \(\in\) читается как «принадлежит».

Если мы хотим задать множество через перечисление элементов, то можно это сделать так:

\
В данном случае множество \(B\) содержит 6 элементов — числа от нуля до пяти.

Приведём примеры множеств.

1. Множество букв русского алфавита:

\

2. Множество всех натуральных чисел:

\

3. Множество всех целых чисел:

\

Также из числовых множеств мы можем вспомнить рациональные числа \(\mathbb{Q}\), действительные (вещественные) числа \(\mathbb{R}\) и комплексные числа \(\mathbb{C}\).

Мы можем взять и рассмотреть не все элементы какого-то множества, а какую-то их часть. Например, взять элементы \(a_1\) и \(a_2\) и объединить их в множество поменьше.

Мы получим множество \(A_1 = \{a_1, a_2\}\), которое является подмножеством множества \(A\). Иначе говоря, множества \(A_1\) включается во множество \(A\):

\

В частности, множество натуральных чисел включается во множество целых — \(\mathbb{N} \subset \mathbb{Z}\). А если продолжить эту цепочку, то можно получить что-то такое:

\

Вот такая пирамижка получается.

9.2.2 Операции над множествами

Над множествами можно производить определённые операции. Во-первых, множества можно складывать, или объединять:

\

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

Во-вторых, множества можно умножать, или находить их пересечение:

\

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

В-третьих, можно искать разность множеств — такая операция называется дополнение:

\

А ещё можно вычитать множества друг из друга, то есть искать их симметрическую разность:

\

У меня снова .

Ну, и самый смак — декартово произведение двух множеств. Пусть у нас есть два множества \(A\) и \(B\). Тогда их декартово произведение представляет собой множество всех возможных упорядоченных пар \((a, b), a \in A, b \in B\).

\

Упорядоченность подразумевает, что если мы будем перемножать \(A \times B\), то будут получаться пары \((a,b)\), а если \(B \times A\), то пары \((b, a)\).

Пример интересного декартова произведения множеств представлен на картинке. Это произведение множества \(\{в, и, к\}\) на множество цветов радуги:

Коньюктивная нормальная форма

Коньюктивная нормальная форма — это преобразование исходного выражения при помощи алгебры логики в следующий вид:

(A1 + A2 + A3 + ...) * (B1 + B2 + B3 + ...) *  (C1 + C2 + C3 + ...) * ...,

A,B,…!A, !B,…

A  B == (A -> B)*(B -> A);    A -> B == !A + B;
!!A == A;  !(A*B) == !A + !B;   !(A+B)  == !A * !B;
A+(B*C) == (A+B)*(A+C);         (B*C)+A == (B+A)*(C+A)

!(BA) * A; #;
#defs; #;
#morgan; #;
#add; #;
#collect; #;
#simplify; #;
#hr;
#true;

cnf[]dnf[]

(C+A)*(B+A+!C); #;
#cnf; #;
#dnf; #;
#cnf; #; #hr;
#true;
#true

4^8=65536

((AB)C)D;
#;
#cnf; #;
//#dnf; #;

save[]; последовательность_преобразований; check[];Logic.saves

!((A(B+!A))(C+A+B*C+D))D->!A;
#save;
#cnf; #;
#check;

cnf

Порядок выполнения операторов

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

• ! (NOT)
• & (AND)
• ^ (XOR)
• | (OR)
• && (условный AND)
• || (условный OR)

Если одинаковые операции стоят по соседству, то раньше выполняется та, что левее.

Первый пример

Вычислим true ^ true & false:

• Выбираем самый приоритетный оператор (если таких больше одного — тот, что левее). У нас самый приоритетный & (он здесь такой один).
• Смотрим, что слева и справа от него: это true и false соответственно.
• Вычисляем выражение true & false — получаем false.
• В исходном выражении заменяем true & false результатом его вычисления (false) — и получаем: true ^ false.
• Вычислив это выражение, получаем результат true.

Или короче:

• true ^ true & false
• true ^ false
• true

Второй пример

Заменим & на &&:

Теперь самый приоритетный оператор в выражении это ^ — и порядок вычислений будет уже другой:

• true ^ true && false
• false && false
• false

Примеры задач с решением

Задача

Группа туристов из 100 человек пробыла в городе N три дня. За это время в ресторане питались 28 туристов, фастфуде — 42, кофейне — 30. И в ресторане, и в фастфуде побывало 10 человек; в ресторане и кофейне — 8; в фастфуде и кофейне — 5. Все во всех трех местах побывали три человека. Сколько туристов питалось в других местах и не посетило ни одного из перечисленных?

Решение

В условии задачи три множества — Р, Ф и К. Туристы, которые пытались в ресторане, фастфуде и кофейне, соответственно. Универсальное множество U — это множество всех туристов группы. Запишем условие задачи, где n(X) — количество элементов множества X.

\(n(U)\;=\;100\\n(Р)\;=\;28,\;n(Ф)\;=\;42,\;n(К)\;=\;30\\n\;(Р\;\cap\;Ф)\;=\;10,\;n(Р\;\cap\;К)\;=\;8,\;n\;(Ф\;\cap\;К)\;=\;5\\n\;(Р\;\cap\;Ф\;\cap\;К)\;=\;3\)

Необходимо найти \(n(Р\;\cup\;Ф\;\cup\;К)\;=\;n\;(U\;\backslash\;(Р\;\cap\;Ф\;\cap\:К))\)

В решении задачи поможет представление данных графически с помощью диаграммы Эйлера-Венна

Составляя ее, важно помнить, что если в \(Р\;\cap\;Ф\;\cap\:К\) три элемента, а в множестве \(Р\;\cap\;Ф\) — 10 элементов, то в диаграмме в месте пересечений множеств Р и Ф мы проставляем 7 элементов, так как 3 элемента уже учтено

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

\(n(Р\;\cup\;Ф\;\cup\;К)\;=\;13\;+\;7\;+\;30\;+5\;+\;3\;+\;2\:+\;20\;=\;80\)

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

\(n(U\;\backslash\;(Р\;\cup\;Ф\;\cup\;К))\;=\;100\;-\;80\;=\;20\)

Ответ: 20 туристов не побывали ни в одном из указанных заведений.

Задача

На олимпиаде по математике школьникам предложили решить три задачи: одну по алгебре, одну по геометрии, одну по тригонометрии. В олимпиаде участвовало 1000 школьников. Результаты олимпиады были следующие: задачу по алгебре решили 800 участников, по геометрии — 700, по тригонометрии — 600. 600 школьников решили задачи по алгебре и геометрии, 500 — по алгебре и тригонометрии, 400 — по геометрии и тригонометрии. 300 человек решили задачи по алгебре, геометрии и тригонометрии. Сколько школьников не решило ни одной задачи?

Решение

Начнем с определения множеств и введения обозначений. В данном случае, их три:

• множество задач по алгебре («А»);
• множество задач по геометрии («Г»);
• множество задач по тригонометрии («Т»).

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

Теперь используя диаграмму, обозначим область, которую необходимо найти:

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

Обозначим искомую область А = 0, Г = 0, Т = 0 как «х».

Найдем остальные области:

1. Область А = 0, Г = 0, Т = 1: школьников нет.
2. Область А = 0, Г = 1, Т = 0: школьников нет.
3. Область А = 0, Г = 1, Т = 1: 100 школьников.
4. Область А = 1, Г = 0, Т = 0: школьников нет.
5. Область А = 1, Г = 0, Т = 1: 200 школьников.
6. Область А = 1, Г = 1, Т = 0: 300 школьников.
7. Область А = 1, Г = 1, Т = 1: 300 школьников.

Теперь внесем значения всех областей в диаграмму:

Определим x:

\(x\;=\;U\;-\;(A\;\cup\;Г\;\cup\;Т)\;\)

При U — универсум

U = 1000

\((A\;\cup\;Г\;\cup\;Т)\;=\; 0 + 0 + 0 + 300 + 300 + 200 + 100 = 900\)

x = 1000 — 900 = 100

Решение задач, примеры

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

Задача 1. Пусть имеется следующее условие: 54 школьника шестых классов занимаются в авиамодельном, музыкальном и танцевальном кружках. Каждый посещает хотя бы один кружок. Музыкой занимаются 32 ученика, 22 — танцами, 34 — авиамоделированием. Участвуют в музыкальном и танцевальном кружках 11 школьников, в музыкальном и авиамоделировании — 21, в танцевальном и авиамоделировании — 12. Сколько учащихся посещают все три кружка?

Рисунок 2

Проект решения предполагает необходимость расписать всех 54 школьников в соответствии с условиями задачи. Известно, что в авиамодельном кружке 34 ученика. Если прибавить к этому число учеников, которые занимаются музыкой, их 32 человека, то получится A ⋃ M, где ⋃ обозначение объединения множеств, будет состоять из 34 + 32… учеников.

Но при взгляде на круги Эйлера (Рисунок 2) становится понятно, что те, кто занимается и музыкой, и авиамоделированием посчитаны дважды. Это область на диаграмме, которая принадлежит и кругу A, и кругу М, таких учеников 21. Значит, объединение множеств A ⋃ M будет 34 + 32 — 21…

Теперь нужно прибавить 22 школьника, занимающихся танцами. A ⋃ M ⋃ T равно 34 + 32 — 21 + 22… Тут опять некоторые ученики оказываются посчитаны дважды. Можно вычесть из общей суммы тех, кто занимается танцами и музыкой — 11 человек и 12 человек, участвующих в авиамодельном и танцевальном кружках одновременно. Функция принимает следующий вид: A ⋃ M ⋃ T будет 34 + 32 — 21 + 22 — 11 — 12…

Но при этом школьники, которые посещают все три кружка, оказались отняты дважды. Их число обозначено x и его надо прибавить один раз к имеющейся формуле. Чтобы решить задачу, требуется определить x из полученного уравнения (Рисунок 3).

54 = 34 + 32 — 21 + 22 — 11 — 12 + х; откуда следует, что x = 10. Ответ: 10.

Рисунок 3

Задача 2. В школьную библиотеку пришло 30 учеников седьмого класса. Из них 15 человек взяли учебник по алгебре, 12 — по русскому языку, 10 человек не взяли ни одного учебника. Сколько учеников получили учебники по алгебре и русскому языку?

Множества на диаграммах представлены на рисунке 4. В большом круге 30 учеников, внутри двух малых 30 — 10 = 20 человек. По условию задачи 15 учеников получили учебник по алгебре, значит, 20 — 15 = 5 учеников получили только учебник по русскому языку. А в условии говорится, что 12 человек взяли учебник по русскому, то есть 12 — 5 = 7 школьников получили учебники и по алгебре, и по русскому. Ответ: 7.

Рисунок 4

Круги Эйлера часто применяются для решения самых разных задач. Они служат для развития способности к логическому мышлению у дошкольников. Большой раздел задач для школьников может решаться с помощью диаграмм. Многие учёные в своих исследованиях тоже обращаются к этому методу, который повышает наглядность решаемых проблем и помогает в их обдумывании. Использование простых фигур позволяет свести решение любой сложной задачи к символической логике и упростить ход рассуждений. Диаграммы могут применяться и в обычной жизни, например при поиске работы. Пересечение кругов «лучше всего получается», «больше всего нравится делать» и «чем можно заработать», возможно, даст нужный результат.

Алгебра высказываний

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

Логическая переменная – это простое высказывание. Логические переменные обозначаются прописными и строчными латинскими буквами (a-z, A-Z) и могут принимать всего два значения – 1, если высказывание истинно, или 0, если высказывание ложно.

 Пример высказываний:

 
 
 
 
 
 
 
 

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

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

Многие люди  не любят сырую погоду.

Пусть А = «Многие люди любят сырую погоду». Получаем логическую функцию F(A) = не А.

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

Логическая формула (логическое выражение) — формула, содержащая лишь логические величины и знаки логических операций. Результатом вычисления логической формулы является ИСТИНА (1) или ЛОЖЬ (0).

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

 

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

1. Логическое умножение (конъюнкция), от лат. konjunctio – связываю:•    Объединение двух (или нескольких) высказываний в одно с помощью союза И;•     в языках программирования — And. •    Принятые обозначения: /\ , •, и, and.•    В алгебре множеств конъюнкции соответствует операция пересечения множеств.
 

Конъюнкция истинна тогда и только тогда, все, входящие в нее высказывания истинны.

Пример: Рассмотрим составное высказывание  «2 • 2 = 4 и 3 • 3 = 10». Выделим простые высказывания:А = «2 • 2 = 4» = 1 (т.к. это истинное высказывание)В = «3 • 3 = 10» = 0 (т.к. это ложное высказывание)Поэтому, логическая функция F(A, B) = A /\ B = 1 /\ 0 = 0 (в соответствии с таблицей истинности), то есть данное составное высказывание ложное.

2. Логическое сложение (дизъюнкция), от лат. disjunctio – различаю:•    Объединение двух (или нескольких) высказываний в одно с помощью союза ИЛИ;•     в языках программирования — Or. •    Обозначение:  \/, +, или, or.•    В алгебре множеств дизъюнкции соответствует операция объединения множеств.
 

Дизъюнкция ложна тогда и только тогда, все, входящие в нее высказывания ложны.

Пример: Рассмотрим составное высказывание  «2 • 2 = 4 или 2 • 2 = 5». Выделим простые выска-зывания:А = «2 • 2 = 4» = 1 (т.к. это истинное высказывание)В = «2 • 2 = 5» = 0 (т.к. это ложное высказывание)Поэтому, логическая функция F(A, B) = A \/ B = 1 \/ 0 = 1 (в соответствии с таблицей истинности), то есть данное составное высказывание истинно.

3. Отрицание (инверсия), от лат. InVersion – переворачиваю:

•    Соответствует частице НЕ, словосочетаниям НЕВЕРНО, ЧТО или НЕ ЯВЛЯЕТСЯ ИСТИНОЙ, ЧТО;•    в языках программирования — Not; •    Обозначение: не А, ¬А, not•    В алгебре множеств логическому отрицанию соответствует операция дополнения до универсального множества.

 
 
 
 
 
 
Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

 Пример:

А = {два умножить на два равно четырем} = 1.

 ¬A= {Неверно, что два умножить на два равно четырем}= 0.

Рассмотрим высказывание А : «Луна — спутник Земли«;  тогда   ¬А будет формулироваться так:  «Луна — не спутник Земли«.

Рассмотрим высказывание: «Неверно, что 4 делится на 3». Обозначим через А простое высказывание «4 делится на 3». Тогда логическая форма отрицания этого высказывания имеет вид ¬А

Приоритет логических операций:

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

Составные логические выражения алгебры высказываний называют формулами.Истинно или ложно значение формулы можно определить законами алгебры логики, не обращаясь к смыслу: F = (0 \/ 1) /\ (¬0 \/ ¬1) = (0 \/ 1) /\ (1 \/ 0) =1 /\ 1=1 — истинаF = (¬0 /\ ¬1) \/ (¬1 \/ ¬1) = (1 /\ 0) \/ (0 \/ 0) = 0 \/ 0 = 0 — ложь