ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРА

ЛОГИКА ЛОГИКА – это наука о формах и способах мышления. Мышление осуществляется через: понятия; понятия; высказывания; высказывания; умозаключения. умозаключения.

ПОНЯТИЕ– ПОНЯТИЕ – форма мышления, которая выделяет существенные признаки предмета или класса предметов, позволяющие отличать их друг от друга. (Пример: прямоугольник - геометрическая фигура у которой все углы прямые и противоположные стороны равны) ПОНЯТИЕ

ВЫСКАЗЫВАНИЕ– ВЫСКАЗЫВАНИЕ – формулировка своего понимания окружающего мира (повествовательное предложение в котором что-либо утверждается или отрицается) (Пример: Париж – столица Франции) ВЫСКАЗЫВАНИЕ

ВЫСКАЗЫВАНИЕ ИСТИННОЕ ЛОЖНОЕ ИСТИННОЕ ЛОЖНОЕ (Пример: Буква «А» - гласная) (Пример: Компьютер был изобретен до нашей эры)

УМОЗАКЛЮЧЕНИЕ УМОЗАКЛЮЧЕНИЕ УМОЗАКЛЮЧЕНИЕ – форма мышления, с помощью которой из одного или нескольких суждений может быть получено новое суждение (знание или вывод). (Пример: любая теорема)

АЛГЕБРА ЛОГИКИ(булева алгебра) АЛГЕБРА ЛОГИКИ (булева алгебра) – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. АЛГЕБРА ЛОГИКИ

ДЖОРДЖ БУЛЬ

ЛОГИЧЕСКОЕ ВЫСКАЗЫВАНИЕ ЛОГИЧЕСКОЕ ВЫСКАЗЫВАНИЕ – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или ложно. ЛОГИЧЕСКОЕ ВЫСКАЗЫВАНИЕ

Сейчас идет дождь. Жирафы летят на север. История – интересный предмет. У квадрата – 10 сторон и все разные. Красиво! В городе N живут 2 миллиона человек. Который час? ВЫСКАЗЫВАНИЕ ИЛИ НЕТ?

ВИДЫ И ОБОЗНАЧЕНИЕ ВЫСКАЗЫВАНИЙ A A – Сейчас идет дождь. B B – Форточка открыта. простые высказывания (элементарные) Любое высказывание может быть ложно (0) или истинно (1). !

СОСТАВНЫЕ ВЫСКАЗЫВАНИЯ СОСТАВНЫЕ ВЫСКАЗЫВАНИЯ строятся из простых с помощью логических связок (операций) «и», «или», «не», «если … то», «тогда и только тогда» и др. СОСТАВНЫЕ ВЫСКАЗЫВАНИЯ A и B A или не B если A, то B не A и B A тогда и только тогда, когда B Сейчас идет дождь и открыта форточка. Сейчас идет дождь или форточка закрыта. Если сейчас идет дождь, то форточка открыта. Сейчас нет дождя и форточка открыта. Дождь идет тогда и только тогда, когда открыта форточка.

ТАБЛИЦА ИСТИННОСТИ ТАБЛИЦА ИСТИННОСТИ – таблица определяющая значение сложного высказывания при всех возможных значениях простых высказываний. ТАБЛИЦА ИСТИННОСТИ

Операция НЕ (инверсия) A«не А» Если высказывание A истинно, то «не А» ложно, и наоборот. таблица истинности операции НЕ также:, not A (Паскаль), ! A (Си) Ане А

Операция И (логическое умножение, конъюнкция) «A и B» АB Высказывание «A и B» истинно тогда и только тогда, когда А и B истинны одновременно. ABА и B также: A·B, A B, A and B (Паскаль), A && B (Си) A B

ABА или B Операция ИЛИ (логическое сложение, дизъюнкция) «A или B» АB Высказывание «A или B» истинно тогда, когда истинно А или B, или оба вместе. 1 0 также: A+B, A B, A or B (Паскаль), A || B (Си)

Операция «ЕСЛИ…,ТО…» (импликация) «A B» АB Высказывание «A B» истинно, если не исключено, что из А следует B. A – «Работник хорошо работает». B – «У работника хорошая зарплата». ABА B

«Если Вася идет гулять, то Маша сидит дома». A – «Вася идет гулять». B – «Маша сидит дома». Маша может пойти гулять (B=0), а может и не пойти (B=1)! ABА B А если Вася не идет гулять? ? Операция «ЕСЛИ…,ТО…» (импликация)

«A B» АB Высказывание «A B» истинно тогда и только тогда, когда А и B равны. Операция «ТОГДА И ТОЛЬКО ТОГДА,…» (эквивалентность) ABА B

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

¬¬FF. 1.Закон двойного отрицания: ¬¬FF. 2.Идемпотентность операций и : F FF; F FF. 3.Коммутативность операций и : F GG F; F GG F. 4.Ассоциативность операций и : F (G Q)(F G) Q; F (G Q)(F G) Q. Основные законы

5.Дистрибутивность каждой из операций и относительно другой: F (G Q)(F G) (F Q); F (G Q)(F G) (F Q). 6.Законы поглощения: F (F G)F; F (F G)F. 7.Законы де Моргана: ¬(F G)¬F ¬G; ¬(F G)¬F ¬G.

F ¬F1. 8.Закон исключенного третьего: F ¬F1. 9.Закон противоречия : F ¬F0. 10.Свойства тавтологии и противоречия: F 1F; F 0F; F 11; F 00; ¬10; ¬ Закон контрапозиции:FG¬G¬F. Основные законы

12.Правило исключения импликации: FG¬F G. 13.Правило исключения эквиваленции: F G(FG) (GF). Основные законы