20. Импликация, эквивалентность, сумма по модулю два 1 курс

20. Импликация, эквивалентность, сумма по модулю два

Импликация, что по латыни обозначает 'тесно связываю', является одной из важных логических операций,
связывающей два высказывания в сложное высказывание с помощью логической связки, которой в обычном языке
в значительной мере соответствует союз "если.., то.." Обозначается этот союз в исчислении высказываний
горизонтальной стрелкой "® ", а в теории множеств знаком "влечёт", "включает" É . Например, А ® В , А É В.

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

А	В	А ® В	А	В	А ® В
и	и	и	1	1	1
и	л	л	1	0	0
л	и	и	0	1	1
л	л	и	0	0	1

            Здесь, первая строка говорит, что истинное высказывание В может вытекать из истинного высказывания А, если А истинно и В истинно, то А ® В истинно.
             вторая строка свидетельствует. что ложное   высказывание не может вытекать из истинного высказывания, следовательно, А ® В ;
              третья строка говорит, что истинное высказывание может вытекать из ложного высказывания, то есть истинность следствия не является доказательством истинности посылки, а значит и формула А ® В истинна.
             четвёртая строка говорит о том. что если высказывание В ложно, то следовательно и высказывание А из которого оно следует является ложным. а значит формула А ® В истинна.

В том случае, когда импликация подчёркивает известное ограничение ("если и только если"), то она символически записывается следующим образом А « В и читается так: "А, если и только если В" . Формула А « В является сокращением записи А ® В Ù В ® А, где Ù знак конъюнкции.

Высказывания, включающие импликацию, могут заменяться равносильными другими высказываниями. Доказательством справедливости замены служат таблицы истинности. Например, равносильность формул (А ® В) и (Ā Ú В) можно усмотреть из следующей таблицы истинности.

Ā	В	А	В	Ā Ú В	А ® В
0	0	1	0	1	1
1	0	0	0	0	0
0	1	1	1	1	1
1	1	0	1	1	1

В логической литературе формулируется целый ряд общезначимых формул, которые истинны при всех значениях, входящих в них переменных. Следует отметить. что формулу А ® В нельзя истолковывать, как "А влечёт В" или "В логически вытекает из А", правильнее читать так "А имплицирует В".

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

Эквивалентность можно записать такими знаками: « , ≡ , ~ ,

Но также, как и в импликации, где союз не выражал смысловой связи двух высказываний, так и в эквивалентности связь "если, и только, если" выражает лишь отношение между А и В по истинностным значениям " истина" и "ложь".. Всякие две истинные формулы исчисления высказывания эквивалентны. Например:

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

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

A ~ B

Соотношение эквивалентности обладает свойствами: 1) симметричности, то есть aRb « bRa "если а эквивалентно b, то и b эквивалентно а". Здесь R - знак отношение.

2) транзитивностью, то есть, если А эквивалентно В, и В эквивалентно С, то и А эквивалентно С.

3) рефлексивностью, что означает, что каждый элемент а эквивалентен самому себе, то есть аRb.

Все известные формулы тождества, включая формулы де Моргана, можно приводить в качестве примера, заменяя знак равенство на знак эквивалентности ~ "тильда".

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

A ~ B

Для этой операции справедливы законы коммутативности, ассоциативности, дистрибутивности. Свойства констант в алгебре Жегалкина: х ×1 =1; х × 0 = 0; х + 0 = 0; Система счисления с основанием, равным двум, является простейшей позиционной системой счисления, которая называется двоичной системой счисление. В этой системе счисления выбраны для изображения любого числа только две цифры - 0 и 1. Все числа, фигурирующие в этой системе счисления, представляют собой набор цифр из единиц и нулей. Поэтому операции сложения двух чисел осуществляются поразрядным сложением по модулю два. При сложении двух единиц в каком-нибудь разряде слагаемых по модулю два мы получаем нуль, а в высший разряд переносим единицу, которая позиционно в два раза больше предыдущего разряда. В теории рассматривается только операция сложения, так все остальные арифметические операции могут быть выражены через операцию суммирования.

Для перевода десятичного числа в двоичный код, производится последовательное деление переводимого числа на два. Остатки от деления образуют последовательность из единиц и нулей. Выстраивая поочерёдно остатки в ряд, получаем исходное число в двоичной форме. Например, 27 : 2 = 13 остаток 1; 13 : 2 = 6 остаток 1; 6 : 2 =3 остаток 0; 3 : 2=1 остаток 1. Таким образом получаем двоичное число: 11011.

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

Например: число (1 000 000 011)₂ = (2⁹ + 2¹ + 2^o)₁₀ = (512 + 2 + 1)₁₀ = 515 Здесь нижний индекс указывает систему счисления.

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