Элементы комбинаторики, теория множеств и математической логики

Логические переменные и логические операции
Простые высказывания в алгебре логики обозначаются заглавными латинскими буквами: А, В, С, D,… и т. д.
Составные высказывания на естественном языке образуются с помощью союзов. В алгебре логики эти союзы заменяются логическими операциями. В соответствии с алгеброй логики любое составное высказывание можно рассматривать как логическую функцию F(А, В, С, …).
Например: F(A,B)= A and B
Логические функции и логические переменные (аргументы) принимают только два значения: «истина», которая обозначается логической единицей – 1 и «ложь», обозначаемая логическим нулем – 0. Логическую функцию называют также предикатом.

Действия, совершаемые над логическими переменными для получения определенных логических функций, называются логическими операциями.
1. Логическая операция ИНВЕРСИЯ (отрицание). В естественных языках соответствует словам неверно, ложь или частице не, в языках программирования обозначается Not, в алгебре логики обозначается
Результат отрицания всегда противоположен значению аргумента.
Например:
F=not(A)
F= ¬ A
F=

2. Логическая операция КОНЪЮНКЦИЯ (логическое умножение). В естественных языках соответствует союзу «И» , в языках программирования обозначается «And» , в алгебре логики обозначается «&» или «Λ» , или « ⋅ » .
Конъюнкция каждым простым высказываниям ставит в соответствие составное высказывание, являющееся только тогда истинным, когда являются истинными простые высказывания, образующие составное высказывание.
Математическая запись данной операции для логических переменных А, В, С, … будет иметь вид: F = A & B & C & …

Пример:
Дана функция F(A, B, C) = A Λ B Λ C.
Определить значение логической функции при условии, что значения переменных А и В истинны, а переменной С – ложно.

Пример:
Дана функция F(A, B, C) = A Λ B Λ C.
Определить значение логической функции при условии, что значения переменных А и В истинны, а переменной С – ложно.
А=1
В=1
С=0
F(A, B, C) = A Λ B Λ C = 1 Λ 1 Λ 0 = 0

3. Логическая операция ДИЗЪЮНКЦИЯ (логическое сложение). В естественных языках соответствует союзу «ИЛИ», в языках программирования обозначается «Or», в алгебре логики обозначается «V» или «+».
Дизъюнкция каждым простым высказываниям ставит в соответствие составное высказывание, являющееся только тогда истинным, когда хотя бы одно из образующих его высказываний является истинным.
Математическая запись данной операции для логических переменных A, В, С, … будет иметь вид:
F = A V B V C …

Пример:
Дана функция F(A, B, C) = A V B V C.
Определить значение логической функции при условии, что значение переменных А и В ложны, а переменной С – истинно.

Пример:
Дана функция F(A, B, C) = A V B V C.
Определить значение логической функции при условии, что значение переменных А и В ложны, а переменной С – истинно.
А=0
В=0
С=1
F(A, B, C) = A V B V C = 0 V 0 V 1 = 1

4. Логическая операция ИМПЛИКАЦИЯ (логическое следование). В естественных языках соответствует обороту речи, «если…, то …» , в языках программирования обозначается «IF», в алгебре логики обозначается «→».
Импликация каждым простым высказываниям ставит в соответствие составное высказывание, являющееся ложным тогда и только тогда, когда первое высказывание истинно, а второе высказывание ложно.
Математическая запись данной операции для двух логических переменных А и В будет иметь вид:
F = A→B.

Пример:
Дана функция F(A, B, C) = A V B → C.
Определить значение логической функции при условии, что значение переменной А истинно, В – ложно, а переменной С – истинно.
А=1
В=0
С=1
F(A, B, C) = A V B → C =

Пример:
Дана функция F(A, B, C) = A V B → C.
Определить значение логической функции при условии, что значение переменной А истинно, В – ложно, а переменной С – истинно.
А=1
В=0
С=1
F(A, B, C) = A V B → C = 1 V 0 → 1 = 1

5. Логическая операция ЭКВИВАЛЕНЦИЯ (логическая равнозначность). В естественных языках соответствует обороту речи «тогда и только тогда», в алгебре логики обозначается «↔», или «≡» .
Эквиваленция каждым простым высказываниям ставит в соответствие составное высказывание, являющееся истинным тогда и только тогда, когда все простые высказывания, образующие составное высказывание, одновременно истинны или одновременно ложны.
Математическая запись данной операции для логических переменных A, В, С… будет иметь вид:
F = A↔B ↔ C ↔ …

Пример:
Дана функция F(A, B, C) = A & ¬ B ↔ C.
Определить значение логической функции при условии, что значение переменной А истинно, В – ложно, а переменной С – истинно.
А=1
В=0
С=1
F(A, B, C) = A & ¬ B ↔ C =

Пример:
Дана функция F(A, B, C) = A & ¬ B ↔ C.
Определить значение логической функции при условии, что значение переменной А истинно, В – ложно, а переменной С – истинно.
А=1
В=0
С=1
F(A, B, C) = A & ¬ B ↔ C = 1 & ¬0 ↔ 1 =
= 1 & 1 ↔ 1 = 1

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

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

Выполним преобразование, например, логической функции
применив соответствующие законы алгебры логики.
C помощью законов алгебры логики можно производить равносильные преобразования логических выражений с целью их упрощения. В алгебре логики на основе принятого соглашения установлены следующие правила (приоритеты) для выполнения логических операций:
первыми выполняются операции в скобках, затем в следующем порядке:
инверсия (отрицание),
конъюнкция ( & ),
дизъюнкция (v),
импликация (→),
эквиваленция (↔).

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

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

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

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

Выполним преобразование, например, логической функции
применив соответствующие законы алгебры логики.
1

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

Логические функции и таблицы истинности
Таблица истинности состоит из двух частей. Первая (левая) часть относится к логическим переменным и содержит полный перечень возможных комбинаций логических переменных А, В, С… и т. д. Вторая (правая) часть этой таблицы определяет выходные состояния как логическую функцию от комбинаций входных величин.
Видеоролик :
https://www.youtube.com/watch?v=R5iuMQFPmI8

Таблицу истинности можно составить для любой логической функции
Видеоролик :
https://www.youtube.com/watch?v=R5iuMQFPmI8

Функция F1 = 0 и называется функцией константы нуля, или генератора нуля.
Функция F2 = A & B называется функцией конъюнкции.
Функция называется функцией запрета по логической переменной А.
Функция F4 = А называется функцией повторения по логической переменной А.
Функция называется функцией запрета по логической переменной В.
Функция F6 = В называется функцией повторения по логической переменной В.
Функция называется функцией исключающее «ИЛИ».
Функция F8 = A v В называется функцией дизъюнкции.
Функция называется функцией Пирса.
Функция называется функцией эквиваленции.
Функция называется функцией отрицания (инверсии) по логической переменной В.
Функция F12 = B →A называется функцией импликации .
Функция называется функцией отрицания (инверсии) по логической переменной А
Функция F14 = A →B называется функцией импликации.
Функция называется функцией Шеффера.
Функция F16 = 1 называется функцией генератора 1.

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

В компьютерах все вычисления выполняются с помощью логических элементов – электронных схем, выполняющих логические операции.
1. Логический элемент НЕ, который называется также инвертором, выполняет логическую операцию отрицания (инверсии).

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

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

В вычислительной технике также часто используется операция исключающее ИЛИ (XOR), которая отличается от обыкновенного ИЛИ только при Х=1 и Y=l.

Памятка

Составим схему, соответствующую выражению

Составим схему, соответствующую выражению

Составим схему, соответствующую выражению
Добавляем элемент И:

Составим схему, соответствующую выражению
Добавляем элемент И:
Ставим элемент НЕ:

Составить логическую схему для следующего логического выражения: F= x V y & x
(пусть x – истина, y – ложь)

Домашнее задание.
Используя законы алгебры логики упростить выражения: