Макинтош и образование:Информатика и ИТ:Элементы логики

Элементы логики [1], [4]

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

История логики начинается с трудов Аристотеля (384-322 гг до н. э.). Традиционная логика опиралась на естественный язык. Во второй половине XIX века ей на смену пришла математическая (или символическая) логика, использующая метод построения специальных формализованных языков (исчислений). Это позволяет избежать двусмысленности и логической неясности естественного языка

Для описания логики функционирования аппаратных и программных средств ВТ используется алгебра логики или emphбулева алгебра (по имени создателя -- Джорджа Буля)

1.1  Классическая логика

Классическая логика -- раздел математической логики, включающий классическую логику высказываний и и ее расширенный вариант -- логику предикатов

Высказывание -- грамматически правильное повествовательное предложение вместе с выражаемым им смыслом. Высказывание является истинным или ложным1.

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

Конъюнкция (результат соединения высказываний с помощью связки <<и>>) дает сложное высказывание, истинное только тогда, когда истинны оба составляющие его высказывания.


Дизъюнкция (результат соединения высказываний с помощью связки <<или>>) дает сложное высказывание, истинное, когда истинно хотя бы одно из составляющих его высказываний.


Строгая дизъюнкция (результат соединения высказываний с помощью связки <<исключающее или>>) дает сложное высказывание, истинное, когда истинно только одно из составляющих его высказываний.


Инверсия (отрицание) (результат применения к высказыванию связки <<не>>) дает сложное высказывание, истинное, когда исходное высказывание ложно.


Импликация (следование) (результат соединения высказываний с помощью связки <<если ... , то>>) дает сложное высказывание, ложное, только когда первое из составляющих его высказываний истинно, а второе -- ложно.


Эквиваленция (результат соединения высказываний с помощью связки <<тогда и только тогда>>) дает сложное высказывание, истинное, когда истинность составляющих его высказываний совпадает.

Язык логики высказываний включает бесконечное множество переменных, представляющих высказывания, и набор символов для обозначения логических связок

  • xy или x & y -- конъюнкция;
  • xy или x + y -- дизъюнкция;
  • xy или xy -- строгая дизъюнкция;
  • x или -- инверсия;
  • xy -- импликация;
  • xy или xy -- эквиваленция.

В логике предикатов в дополнение к средствам логики высказываний вводятся логические операторы -- кванторы общности (<<для всех>>) и существования (<<существует>>)

1.2  Таблицы истинности

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

Table 1: Таблицы истинности для логических связок

A B AB AB AB
F F F F T
F T F T T
T F F T F
T T T T T

1.3  Законы алгебры логики [2]

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


Логические выражения, истинные при любых значениях истинности входящих в них переменных, называют тавтологиями (от греч. <<tauto>> -- то же самое и <<logos>> -- слово).

Свойства конъюнкции и дизъюнкции

a + 0 = a;     a & 0 = 0;     a + 1 = 1;     a & 1 = a

Законы коммутативности (переместительные)

a + b = b + a;     a & b = b & a

Законы ассоциативности (сочетательные)

(a + b) + c = a + (b + c);    (a & b) & c = a & (b & c)

Законы дистрибутивности (распределительные)

a & (b + c) = (a & b) + (a & c);     a + (b & c) = (a + b) & (a + c)

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

a & b
 
 =
a
 
 +
b
 
 ;    
a + b
 
 =
a
 
 &
b
 

Закон двойного отрицания (инволюции)

a
 
 
 = a

Закон противоречия

a &
a
 
 = 0

Закон исключенного третьего

a +
a
 
 = 1

Законы идемпотентности (исключения повторений)

a + a = a;     a & a = a

Законы поглощения

a & (a + b) = a;    a + (a & b) = a

Задача 1 [3] Приемная комиссия в составе председателя и трех помощников решает судьбу абитуриентов большинством голосов. В случае равного распределения голосов решающим является голос председателя. Построить автомат, определяющий решение комиссии в соответствии с приведенными условиями голосования.

Литература

[1]
Д. П. Горский, А. А. Ивин, А. Л. Никифоров. Краткий словарь по логике. М.: Просвещение, 1991.
[2]
В. М. Паршин. Теория и практика алгебры логики//Информатика и образование. 1999. 6 с. 11-20, 7 с. 18-24
[3]
В. И. Лобанов. Синтез и минимизация комбинационных схем//Информатика и образование. 2000. 5 с. 60-63.
[4]
М. В. Танцорова. Изучаем логику в начальной школе//Информатика и образование. 2000. 5 с. 86-95.

Примечания:

1 в классической логике

File translated from TEX by TTH, version 2.25.
On 14 Jun 2002, 23:16.

[Титульная страница][Макинтош][Информатика и ИТ]
Hosted by uCoz