Логика в информатике

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

логики

Логика как наука

Логика (

от греч. Logos – слово, понятие,

рассуждение, разум

) – наука о законах и

формах рационального мышления.

Мыслить логично – значит мыслить

точно и последовательно, не допуская

противоречий в своих рассуждениях,

уметь вскрывать логические ошибки.

Формы человеческого мышления



Понятие



Высказывание



Умозаключение

Понятие

Понятие – форма мышления, в которой отражаются

отличительные существенные признаки предметов.

Свойства понятия:

1.

содержание – необходимые и достаточные

признаки, для выделения данного объекта из множества

других.

2.

объем – множество объектов, каждому из которых

принадлежат признаки, составляющие содержание

понятия.

Чем богаче содержание, тем меньше объём понятия!

Отношения между понятиями

Далёкие друг от друга по своему

содержанию понятия, не имеющие общих

признаков, называются несравнимыми,

остальные понятия называются сравнимыми.

Отношения между сравнимыми понятиями

принято графически изображать с помощью

кругов Эйлера.

Совокупность всех существующих множеств

образует всеобщее универсальное

множество 1, логически противоположное

заданному (диаграмма Эйлера – Венна)

Высказывание

Высказывание (суждение, утверждение) –

это форма мышления, в которой что-либо

утверждается или отрицается о предметах, их

свойствах или отношениях между ними.

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

Бывают

простыми и составными,

общими и частными,

истинными или ложными.

Логическая форма высказываний

S – субъект (о чем говорится),

P – предикат (что говорится),

Есть (не есть, является, состоит и т.д.) – связка.

S есть (не есть) P

Умозаключение

Умозаключение – форма мышления, с

помощью которой из одного или нескольких

суждений-посылок, по определенным правилам

может быть получено новое суждение

-заключение (вывод).

Посылками могут быть только истинные

суждения.

Формы умозаключений

Форма может быть логически правильной или

неправильной.

Пример:

Все S есть P

Некоторые A есть S

Некоторые A есть P

Все S есть P

Некоторые A есть P

Некоторые A есть S

Все люди смертны

Сократ - человек

Сократ - смертен

Все зебры полосаты

Это животное полосато

Это животное - зебра

Алгебра высказываний

Алгебра высказываний - это раздел

математической логики, изучающий строение

сложных логических высказываний и способы

установления их истинности с помощью

алгебраических методов.

Обозначение высказываний:

А = Москва – столица России. А=1 – истинное

высказывание.

Х = 9 кратно 2.

Х=0 – ложное

высказывание.

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

Логические операции – способ построения

сложного высказывания из данных высказываний,

при котором значения истинности сложного

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

истинности исходных высказываний.



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



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



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



Логическое следование (импликация)



Логическое равенство (эквивалентность)

Логическое отрицание

(инверсия)



Образуется из высказывания с помощью добавления

частицы «не» к сказуемому или использования оборота

речи «неверно, что…»



Обозначение: не А, ¬А, А, not А



Таблица истинности:

А

не А

0

1

Инверсия высказывания истинна, когда высказывание

ложно, и ложна, когда высказывание истинно.

Логическое умножение

(конъюнкция)



Образуется соединением двух высказываний в одно с

помощью союза «и».



Обозначение: А и В, А & В, А



В, А and В



Таблица истинности:

А

В

А & В

0

0

0

1

1

0

1

1

Конъюнкция двух высказываний истинна тогда и

только тогда, когда оба высказывания истинны.

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



Образуется соединением двух высказываний в одно с

помощью союза «или».



Обозначение: А или В, А



В, А or В



Таблица истинности:

А

В

А



В

0

0

0

1

1

0

1

1

Дизъюнкция двух высказываний ложна тогда и

только тогда, когда оба высказывания ложны.

Логическое следование

(импликация)



Образуется соединением двух высказываний в одно с

помощью оборота речи «если …, то…».



Обозначение: А

→

В



Таблица истинности:

А

В

А

→

В

0

0

0

1

1

0

1

1

Импликация двух высказываний ложна тогда и

только тогда, когда из истинного высказывания

следует ложное.

Логическое равенство

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



Образуется соединением двух высказываний в одно с

помощью оборота речи « …тогда и только тогда,

когда…».



Обозначение: А

~

В, А

≡

В, А

↔

В



Таблица истинности:

А

В

А

↔

В

0

0

0

1

1

0

1

1

Эквивалентность двух высказываний истинна

тогда и только тогда, когда оба высказывания

истинны или оба ложны.

Задание

Выделите из составных высказываний простые.

Обозначьте каждое из них буквой; запишите с помощью

логических операций каждое составное высказывание:



Число 376 четное и трехзначное



Неверно, что Солнце движется вокруг Земли.



Если сумма цифр числа делится на 3, то число

делится на 3.



Оценка «5» ставится тогда и только тогда,

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

Найдите значения логических

выражений

1.

(1



1) & (1



0)

2.

(1



0)



(1



0)

3.

(0



0)

↔

(1



0)

4.

(1



1)

→

(1 & 0)

5.

(1 & 0) & (1



0)