Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Основы математической логики





Основные определения

Логика – наука о формах и способах мышления.

Логика как наука впервые была предложена древнегреческим ученым Аристотелем, (384 -322 гг. до н.э., ученик Платона, 343г до н.э воспитатель Александра Македонского, основал Ликей, или лицей, определенную форму образования, дошедшую до нашего времени, основоположник формальной логики, создал понятийный аппарат, который пронизывает философский лексикон и сам стиль научного мышления).

Мышление всегда осуществляется в различных формах:

Основными формами мышления являются:

Понятие, высказывание, умозаключение.

Понятие – это форма мышления, фиксирующая основные, существенные признаки объекта.

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

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

В алгебре высказываний высказывания обозначаются именами логических переменных а,b,c, которые могут принимать лишь два значения:

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

ЛЕЙБНИЦ Готфрид Вильгельм немецкий философ, математик, физик, языковед. Предвосхитил принципы современной математической логики ("Об искусстве комбинаторики", 1666). Один из создателей дифференциального и интегрального исчислений.

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



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

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

Инверсия, дизъюнкция, конъюнкция, импликация, эквивалентность, неравнозначность и др.

Логическое умножение (конъюнкция)

Объединение двух (или нескольких) высказываний в одно с помощью союза «и».

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

С точки зрения записи конъюнкция обозначается значками ^ или &.

F=A^B,

где F – функция, являющаяся конъюнкцией двух переменных, A, B – логические переменные, которые могут принимать значения «истина» (1) и «ложь» (0).

Для определения операций широко используются так называемые таблицы истинности, с помощью таблиц истинности легко понять, как на каких наборах функция принимает то, или иное значение. В нашем случае конъюнкция оперирует двумя операндами. Значит, мы можем перебрать все операнды и записать все возможные комбинации (наборы) операндов и записать их в таблицу. В третьем столбце записывается результат логической операции в данном случае конъюнкции. Мы видим, что только 4 столбец имеет значение 1.

Таблица истинности функции логического умножения

A B F=A^B

 

Логическое сложение (дизъюнкция)

Объединение двух (или нескольких) высказываний в одно с помощью союза «или».

Составное высказывание, образованное с помощью дизъюнкции, истинно тогда, когда истинно хотя бы одно, входящих в него простых высказывания.

С точки зрения записи дизъюнкция обозначается значками v или +.

F=A v B,

где F – функция, являющаяся дизъюнкция двух переменных, A, B – логические переменные, которые могут принимать значения «истина» (1) и «ложь» (0).

A B F=AvB

 

Логическое отрицание (инверсия)

Присоединение частицы «не» к высказыванию.

Инверсия делает истинное высказывание ложным и, наоборот, ложное истинным.

Инверсия обозначается А, либо !А, либо ~А.

F=!A

A F=!A

 

Импликация («если … то»)

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

Пример. «Любишь кататься, люби и саночки возить».

F= А®В

A B F= А®В

 

А®В

Эквивалентность («если и только если)

A B F= А«В

 

А«В=!А !В v В^А

Неравнозначность (исключающее или) («либо … либо»)

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

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

A B F= АÅВ

 

АÅВ=!А ^В v А^!В= !(А«В)

Законы логики

Закон тождества

Всякое высказывание тождественно самому себе

А=А

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

А^!А =0

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

Аv!А =1

Закон двойного отрицания

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

!!А =А

Законы де Моргана

Логические законы, связывающие с помощью отрицания высказывания, образованные с помощью союзов «и» и «или».

Отрицание дизъюнкций, есть конъюнкция отрицаний:

!(АvВ)=!А^!В


Отрицание конъюнкций, есть дизъюнкция отрицаний:

!(А^В)=!Аv!В

 

Закон коммутативности (переместительный) – от изменения мест переменных значение функции не меняется.

 

Логическое умножение Логическое сложение
А^В= В ^ А АvВ= ВvА

 

Закон ассоциативности (сочетательный) – от изменения первоочередности вычислении значение функции не меняется.

Логическое умножение Логическое сложение
(А^В)^С= А ^(В ^ С) (АvВ)vС= Аv(ВvС)

 

Закон дистрибутивности – каким образом раскрываются скобки при совершении сложения и умножения.

Дистрибутивность умножения относительно сложения Дистрибутивность сложения относительно умножения
ab+ac=a(b+c) – в алгебре (А^В)v(А^ С)= А ^(В v С)   (АvВ)^ (АvС)= Аv(В^С)

 

Закон идемпотентности (отсутствие степеней и коэффициентов) – сложение и умножение одних и тех же переменных равно самим переменным.

Логическое умножение Логическое сложение
А^А= А АvА= А

 

Свойства констант 0 и 1:

!0=1; !1=0; 1ÅА=!А; 0ÅА=А; АÅ!А=1

Логическое умножение Логическое сложение
А^1= А А^0= 0 Аv1= 1 Аv0= А

 

Решение логической задачи:

Определите истинность составного высказывания

(2*2=4 и 3*3=10) или (2*2=5 и 3*3=9)

1. Заменить простые высказывания логическими переменными и установить их истинность или ложность.

А: «2*2=4» - истинно (1)

В: «3*3=10» - ложно (0)

С: «2*2=5» - ложно (0)

D: «3*3=9» - истинно (1)

2. Заменить логические связи «и» и «или» операциями умножения и логического сложения. Тогда высказывание примет вид следуюшего логического выражения:

(А^В) v(С^D)

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

(1^0) v(0^1)=0 v0=0

Результат: составное высказывание ложно.

 

 

Алгоритм и его свойства

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

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

Само слово «алгоритм» происходит от algorithmi - латинской формы написания имени великого математика IX века аль-Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами и понимали только правила выполнения четырех арифметических действий над многозначными числами.









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2019 zdamsam.ru Размещенные материалы защищены законодательством РФ.