Xreferat.com » Рефераты по математике » Математическая логика

Математическая логика

Введение


Тема контрольной работы «Математическая логика».

БУЛЬ или БУЛ, а также БУУЛ, Джордж (1815-1864) – английский математик, который считается основоположником математической логики.

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

Формализация рассуждений восходит к Аристотелю. Современный вид аристотелева (формальная) логика приобрела во второй половине XIX века в сочинении Джорджа Буля “Законы мысли”.

Интенсивно математическая логика начала развиваться в 50-е годы XX века в связи с бурным развитием цифровой техники.

1. Элементы математической логика


Основными разделами математической логики являются исчисление высказываний и исчисление предикатов.

Высказывание – есть предложение, которое может быть либо истинно, либо ложно.

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

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

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

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


1.1 Основные понятия алгебры логики


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

В алгебре логики интересуются лишь истинностным значением высказываний. Истинностные значения принято обозначать:

1 (истина) 0 (ложь).

Каждой логической операции соответствует функция, принимающая значения 1 или 0, аргументы которой также принимают значения 1 или 0.

Такие функции называются логическими или булевыми, или функциями алгебры логики (ФАЛ). При этом логическая (булева) переменная x может принимать только два значения: Математическая логика.

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

В этом случае алгебру логики можно определить, как совокупность множества логических функций с заданными в нем всевозможными логическими операциями. Таким логическим операциям, как конъюнкция (читается И), дизъюнкция (ИЛИ), импликация, эквивалентность, отрицание (НЕ), соответствуют логические функции, для которых приняты обозначения Математическая логика(&, ·), Математическая логика~, – (Математическая логика), и имеет место таблица истинности:


Математическая логика

Математическая логика

Математическая логика

Математическая логика

Математическая логика

Математическая логика

x~y
0 0 0 0 1 1 1
0 1 0 1 1 1 0
1 0 0 1 0 0 0
1 1 1 1 1 0 1

Это табличный способ задания ФАЛ. Наряду с ними применяется задание функций с помощью формул в языке, содержащем переменные x, y, …, z (возможно индексированные) и символы некоторых конкретных функций – аналитический способ задания ФАЛ.

Наиболее употребительным является язык,содержащий логические символы Математическая логика ~, –. Формулы этого языка определяются следующим образом:

1) все переменные есть формулы;

2) если P и Q – формулы, то Математическая логика P ~ Q, Математическая логика - фор-мулы.

Например, выражение Математическая логика~Математическая логика - формула. Если переменным x, y, z придать значения из двоичного набора 0, 1 и провести вычисления в соответствии с операциями, указанными в формуле, то получим значение 0 или 1.

Говорят, что формула реализует функцию. Так формула Математическая логика~Математическая логика реализует функцию h(x, y, z):

x y z h(x, y, z)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0

Пусть P и Q – формулы, которые реализуют функции f (x1, x2, …, xn) и g (x1, x2, …, xn). Формулы равны: P = Q, если функции f и g совпадают, т.е. совпадают их таблицы истинности. Алгебра, основным множеством которой является все множество логических функций, а операциями – дизъюнкция, конъюнкция и отрицание, называется булевой алгеброй логических функций.

Приведем законы и тождества, определяющие операции Математическая логика– и их связь с операциями Математическая логика, ~:

1. Идемпотентность конъюнкции и дизъюнкции:


Математическая логика.


2. Коммутативность конъюнкции и дизъюнкции:


Математическая логика.


3. Ассоциативность конъюнкции и дизъюнкции:


Математическая логика.


4. Дистрибутивность конъюнкции относительно дизъюнкции и дизъюнкции относительно конъюнкции:

Математическая логика.


5. Двойное отрицание:

Математическая логика.


6. Законы де Моргана:


Математическая логика=Математическая логика, Математическая логика=Математическая логика.


7. Склеивание:


Математическая логика.


8. Поглощение


Математическая логика.


9. Действия с константами 0 и 1:


Математическая логика.


10. Законы Блейка-Порецкого:


Математическая логика.


11. Связь импликации Математическая логика с отрицанием – и дизъюнкцией Математическая логика:


Математическая логика.

12. Связь эквивалентности ~ с дизъюнкцией Математическая логика, конъюнкцией Математическая логика и отрицанием:


Математическая логика~ y =Математическая логика.


Всякая функция алгебры логики может быть реализована некоторой формулой языка с символами Математическая логика~, –.


1.2 Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ)Математическая логика


ДНФ и КНФ играют особую роль в алгебре логики и ее приложениях. Введем обозначение:


Математическая логика


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

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

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ):


Математическая логика.


Формула вида Математическая логика называется элементарной дизъюнкцией.

Всякая конъюнкция элементарных дизъюнкций называется конъюктивной нормальной формой (КНФ):


Математическая логика.


Пример.

Привести формулу Математическая логика~z к ДНФ и КНФ.

1) Приведем формулу к ДНФ (последовательно: на основании определений операций импликации и эквивалентности, законов де Моргана и дистрибутивности):


Математическая логика~ Математическая логика~Математическая логика((Математическая логика)Математическая логика=

Математическая логика.


2) Применив закон дистрибутивности к последнему выражению, получим КНФ:


Математическая логика


Совершенной ДНФ (СДНФ) называется ДНФ, в которой нет равных элементарных конъюнкций и все элементарные конъюнкции содержат одни и те же переменные, причем каждую переменную – только один раз (включая вхождения под знаком отрицания).

Совершенная КНФ (СКНФ) определяется как такая КНФ, в которой нет одинаковых сомножителей; все сомножители содержат одни и те же переменные, причем каждую переменную – только один раз.

Для каждой ФАЛ Математическая логика можно построить реализующую ее СДНФ:

Математическая логика,


где дизъюнкция берется по тем двоичным наборам, на которых f = 1.

Каждая функция алгебры логики Математическая логика реализуется следующей СКНФ:


Математическая логика


Пример.

Функция h(x, y, z), рассмотренная ранее, имеет следующую СДНФ (выписывается по единичным значениям) и СКНФ (выписывается по нулевым значениям):


1

Математическая логика

0

Математическая логика;


x y z h(x,y,z)
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0

Пример.

Построить СДНФ и СКНФ будевой функции f(x1, x2, x3), заданной таблицей истинности


x1 x2 x3 f(x1,x2,x3) x1 x2 x3 f(x1,x2,x3)
0 0 0 1 1 0 0 0
0 0 1 0 1 0 1 1
0 1 0 1 1 1 0 0
0 1 1 0 1 1 1 1

Математическая логика

Математическая логика.


Разложение булевой функции Математическая логика по k переменным x1, x2,…, xk называется разложением Шеннона.


1.3 Теорема Шеннона


Любая булева функция Математическая логика представима в виде разложе-ния Шеннона:


Математическая логика


где Математическая логика, Математическая логика - первичные термы.

Пример.

Пусть п = 4, k = 2. Тогда разложение Шеннона будет иметь вид


Математическая логика

Следствие.

Предельное разложение Шеннона (k = n) булевой функции Математическая логика имеет вид


Математическая логика.


Предельное разложение Шеннона булевой функции Математическая логика является ее СДНФ.

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

по k переменным


Математическая логика


двойственное предельное разложение


Математическая логика.


Двойственное предельное разложение Шеннона булевой функции Математическая логика является ее СКНФ.

2 Булевы функции двух переменных


Рассмотрим простой бинарный элемент – выключатель, который имеет два состояния. Если данный выключатель контролируется входной переменной х,то говорят, что он выключен (открыт) при х = 0 и включен (закрыт) при х = 1, как показано на рис. 1:


Математическая логика

х = 0 х = 1

Рис. 1 - Два состояния выключателя


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


Математическая логика

х

Рис. 2 - Графическое обозначение выключателя


Рассмотрим соединения лампы с источником питания, представленные следующими схемами:


Математическая логика

Рис. 3 - Лампа, управляемая выключателем: а – простое соединение с батареей; б – использование заземления, как обратной связи

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


2.1 Булевы функции от двух переменных


Рассмотрим теперь возможность использования двух выключателей для управления состоянием лампы. Пусть х1 и х2 – управляющие переменные (входы) для этих выключателей. Выключатели могут быть соединены последовательно или параллельно, как показано на рис. 4:


Математическая логика

Рис. 4 - Две основные функции: а – последовательное соединение (функция логического умножения AND); б – параллельное соединение (функция логического сложения OR)


2.2 Последовательное соединение двух выключателей


При последовательном соединении лампа будет светиться только, если оба выключателя включены (одновременно). Это поведение может быть описано выражением: Математическая логика, где L = 1 при х1 = х2 = 1,

L = 0 в противном случае.

Символ Математическая логика называется AND-оператором. Говорят, что схема на рис. 3.4,а реализует логическую AND-функцию (логическое умножение).


2.3 Параллельное соединение двух выключателей


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

Математическая логика, где L = 1 при х1 = 1 или х2 = 1, или х1 = х2 = 1; L = 0 при х1 = х2 = 0.

Символ Математическая логика называется OR-оператором. Говорят, что схема на рис. 4,б реализует логическую OR-функцию (логическое сложение).

В приведенных выше выражениях для AND и OR реализует результат (выход) Математическая логика есть логическая функция с двумя входными переменными. Функции AND и OR являются двумя наиболее важными логическими функциями. Вместе с некоторыми другими простыми функциями они могут быть использованы как составные части (строительные блоки) для реализации логических схем.

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


Математическая логика.


Лампа горит, если х3 = 1 и одновременно равны 1 либо х1, либо х2 (х1 = 1 или х2 = 1)

Математическая логика

Рис. 5 - Последовательно-параллельное соединение выключателей


2.4 Инверсия


Пусть лампа подсоединяется к источнику питания так, как показано на рис. 6:


Математическая логика

Рис. 6 - Инвертирующая схема


В этом случае выключатель соединяется параллельно с лампой. Лампа будет гореть, когда выключатель выключен. Формально такое функци- ональное поведение выражается: Математическая логика, где L = 1 при х = 0 и L = 0 при х = 1. Значение этой функции обратно значению входной переменной.

Вместо слова инверсия существует более общий термин отрицание.

Таким образом, Математическая логика есть отрицание х: Математическая логика. Символ Ї называют NOT-оператором.

Количество логических функций в зависимости от числа переменных равно Математическая логика. Булевых функций одной переменной – четыре:


x f0 f1 f2 f3
0 0 0 1 1
1 0 1 0 1

Индекс I функциональной переменной fi, I = 0, 1, 2, 3, равен десятичному эквивалентному набору значений этой функции, читаемому сверху вниз.

Функции f0(x) и f3(x) – константы 0 и 1 соответственно. Их значения не зависят от значения переменной х. Функция f1(x) “ повторяет “ х: f1(x) = x.

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

Булевых функций двух переменных – шестнадцать:


x1 x2 f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Индекс I функциональной переменной fi, I = 0, 1, 2, …, 15, равен десятичному эквивалентному набору значений этой функции, читаемому сверху вниз. Приведем эти булевы функции:


Математическая логика - константа ноль;

Математическая логика - конъюнкция;

Математическая логика х1 –|→ Математическая логика - левая коимпликация (читается «не если х1, то х2», префикс ко – от лат. conversus – обратный);

Математическая логика;

Математическая логиках1 ←|– х2 - правая коимпликация;

Математическая логика;

Математическая логика- сложение по модулю два или функция неравнозначности, неэквивалентности;


Математическая логика - дизъюнкция;

Математическая логиках1 ◦ х2 = х1 ↓ х2 - функция Вебба (Пирса);

Математическая логика х1 ~ х2 – функция эквивалентности, равнозначности;

Математическая логика - отрицание х2;

Математическая логика - правая импликация (читается « если х2, то х1»);

Математическая логика - отрицание х1;

Математическая логика - левая импликация (читается «если х1, то х2»);

Математическая логика - функция Шеффера;

Математическая логика - константа единица.


2.5 Свойства элементарных функций алгебры логики


2.5.1 Функция сложения по модулю два (по mod 2)

Пусть Математическая логика Операция Математическая логика “сложениe по mod p “ определяется следующим образом: а Математическая логика b = c, где с – остаток от деления на p числа a + b. Например, если р = 7, то Математическая логика. Тогда Математическая логика, Математическая логика.

При сложении по mod 2: р = 2, Математическая логика. Тогда при а = х1, b = x2 получим:

Математическая логика

х1 х2

Математическая логика

0 0 0
0 1 1
1 0 1
1 1 0

Математическая логика.


Справедливы коммутативный и ассоциативный законы. Дистрибутивный закон имеет вид:


Математическая логика


Аксиомы: Математическая логика

Связь

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: