Презентация на тему Элементы математической логики

положено греческим философом Аристотелем, 384-322 гг. до н.э. Он

основоположник формальной логики. Впервые перевести логику на язык математики предложил немецкий математик Г. Лейбниц в конце ХVII века. Эту идею впервые реализовал англ.
математик Дж. Буль (1815 – 1864г.).
Буль создал алгебру, в которой буквами м
обозначены высказывания, и это привело
к алгебре высказываний.
Алгебра логики находит непосредственное и широкое применение при разработке средств электронной и вычислительной техники.

в соответствие одно из двух значений – истина или

ложь. Высказывания строятся над множеством {B,¬, ∧, ∨, 0, 1}, где B — непустое множество, над элементами которого определены три операции: ¬ - отрицание (унарная операция), ∧ - конъюнкция (бинарная), ∨ - дизъюнкция (бинарная),
а также константы — логический ноль 0 и логическая единица 1.
B = {Ложь, Истина}. Для B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трёх выбранных операций.

истинным, если высказывание А ложно, и ложным, если высказывание

А истинно. Обозначается отрицание или ¬ А и читается “не А” или “неверно, что А”. Логические значения высказываний можно описать с помощью таблицы истинности, где 0 означает ложь, а 1 – истину. Таблица истинности для отрицания имеет вид:


Двойное отрицание высказывания А совпадает с самим высказыванием А.

новое высказывание, которое считается истинным, если оба высказывания А,

В истины, и ложным, если хотя бы одно из них ложно. Обозначается конъюнкция по-разному. Например, А×B, AB, А∧В, А&B, А⋅B, читается “А и В”. Логические значения конъюнкции описываются следующей таблицей истинности:

новое высказывание, которое считается истинным, если хотя бы одно

из высказываний истинно, и ложным, если они оба ложны. Дизъюнкция высказываний A, B обозначается символом А ∨ В, (А + В) читается «A или B». Высказывания A, B при этом называются членами дизъюнкции. Логические значения дизъюнкции описываются следующей таблицей истинности:

которое считается ложным, если A истинно, а B -

ложно, и истинным во всех остальных случаях. Обозначается символом A→B, читается «Если A, то B» или «из A следует B». При этом высказывание A называется условием или посылкой, высказывание В – следствием или заключением, высказывание А→В следованием или импликацией.
Таблица истинности:

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

новое высказывание, которое считается истинным, когда оба высказывания А,

В либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях. Эквиваленция высказываний А, В обозначается символом А↔В, читается «для того, чтобы В, необходимо и достаточно, чтобы А», или «А тогда и только тогда, когда В».
Таблица истинности

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

логики:
Выполнение операций в скобках
Операция логического отрицания
Операция логического умножения
Операция логического

сложения
Операция импликации
Операция эквивалентности
Операции с равным приоритетом выполняются слева направо.

С и основанием АВ равнобедренный тогда и только тогда,

когда ∠A = ∠B » является истинным, так как высказывания «Треугольник АВС с вершиной в точке С и основанием АВ равнобедренный» и «В равнобедренном треугольнике АВС с вершиной в точке С и основанием АВ ∠A = ∠B» либо одновременно истинны, либо одновременно ложны.
Эквивалентность играет важную роль в математических доказательствах. Известно, что значительное число теорем математики формулируется в форме необходимых и достаточных условий, то есть в форме эквивалентности. В этом случае, зная об истинности или ложности одного из двух элементов эквивалентности и доказав истинности самой эквивалентности, мы заключаем об истинности или ложности второго члена эквивалентности.

В - высказывание «Вася любит математику». Рассмотрим словесную формулировку

высказываний: 1) А∨В; 2) ; 3) A → B;
4) 5) 6)
Решение:
1) «Вася изучает программирование или любит математику».
2) «Вася не изучает программирование и не любит математику».
3) «Если Вася изучает программирование, то он любит математику».
4) «Неверно, что если Вася изучает программирование, то он любит математику».

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

полностью с помощью таблицы истинности. Например, для формулы
таблица истинности имеет вид:

иметь 23 = 8 строк, и формула принимает 8

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

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

значения на любом наборе значений элементарных высказываний, входящих в формулу. Запись A=B означает, что формулы А и В равносильны. Например, очевидно, что равносильны формулы:
Х=X; Х&Х=X; Х&0 =0; Х∨1=1; Х∨ =1; X∨Х=X; X&1=X; X∨0=X; X& =0.
Легко видеть, что если А = В, то .

если она принимает значение 1 при всех значениях входящих

в нее переменных. Например, тождественно истинной является формула X→(Y→X), что можно проверить, построив таблицу истинности.
Формула называется тождественно ложной, если она принимает значение ноль при всех значениях входящих в нее переменных. Как уже отмечалось , то есть формула тождественно ложная.

B=A (симметрично);
Если А=В и B=С, то A=С (транзитивно).

Между понятиями

равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула А↔В тавтология (то есть тождественно истинная), и, обратно, если формула А↔В тавтология, то формулы А и В равносильны.

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

две логических операции: конъюнкцию и отрицание или дизъюнкцию и отрицание.

X⋅Y=(X|Y)|(X|Y). Из этих двух равносильностей следует, что всякая формула

алгебры логики может быть заменена равносильной формулой, содержащей только операцию «штрих Шеффера». Отметим, что X|Y = . Аналогично операции «штрих Шеффера» может быть использована операция, называемая «стрелкой Пирса»:

форме и в конъюнктивной форме, существует свойство симметрии: если

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

Закон двойственности

переменных


A∨B⋅C⋅D⋅…⋅P = (A∨B)⋅(A∨C)⋅(A∨D)⋅ … ⋅(A∨P) и

A⋅(B∨C∨D∨…∨P) = A⋅B∨A⋅C∨A⋅D∨…∨A⋅P


А∨ A⋅B ∨ A⋅B⋅С⋅D = A;
A⋅(A∨C∨D∨…∨P) = A;

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

значения на любом наборе значений элементарных высказываний, входящих в формулу. Запись A=B означает, что формулы А и В равносильны. Например, очевидно, что равносильны формулы:
Х=X; Х&Х=X; Х&0 =0; Х∨1=1; Х∨ =1; X∨Х=X; X&1=X; X∨0=X; X& =0.
Легко видеть, что если А = В, то .

ДНФ, удовлетворяющая условиям:
Все элементарные конъюнкции различны;
Нет нулевых конъюнкций;
Ни одна

из элементарных конъюнкций не повторяется;
Каждая элементарная конъюнкция содержит все переменные или их отрицания.
Аналогичны условия для СКНФ.
СДНФ и СКНФ используются при проектировании элементов и узлов компьютера

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

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





СКНФ. Для всех наборов переменных, на которых функция принимает нулевые значения, записываются конъюнкции этих переменных, инвертируя те переменные, которым соответствуют единичные значения. Затем дизъюнкции соединяют знаком конъюнкции.

в различных системах счисления: A=16(10), B=21(8), C=12(10). Выполните следующие

логические операции: AB+C. Ответ напишите в шестнадцатеричной системе счисления и в десятичной системе.
3. Постройте таблицу истинности для логической функции
.
4. Построить логическую функцию по заданной таблице истинности, которая имеет нулевые значения при следующих наборах переменных A, B, C: (001), (010), (011), (110).