Кто создал алгебру логики

Идёт приём заявок

Подать заявку

Для учеников 1-11 классов и дошкольников

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

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

Джордж Буль родился в Линкольне (Англия) в семье мелкого торговца. Материальное положение его родителей было тяжелым, поэтому Джордж смог окончить только начальную школу для детей бедняков; в других учебных заведениях он не учился. Этим отчасти и объясняется, что, не связанный традицией, он пошел в науке собственным путем. Буль самостоятельно изучал латынь, древнегреческий, немецкий и французский языки, изучил философские трактаты. С ранних лет Буль искал работу, оставляющую возможности для самообразования. После многих неудачных попыток Булю удалось открыть маленькую начальную школу, в которой он преподавал сам. Школьные учебники по математике привели его в ужас своей нестрогостью и нелогичностью, Буль вынужден был обратиться к сочинениям классиков науки и самостоятельно проштудировать обширные труды Лапласса и Лагранжа.

В связи с этим у него появились первые самостоятельные идеи. Результаты своих исследований Буль сообщил в письмах профессорам математики (Д.Грегори и А. де Моргану) знаменитого Кембриджского университета и вскоре получил известность как оригинально мыслящий математик. В 1849 году в г. Корк (Ирландия) открылось новое высшее учебное заведение — Куинз-колледж, по рекомендации коллег-математиков Буль получил здесь профессуру, которую сохранил до своей смерти в 1864 году. Только здесь он получил возможность не только обеспечить родителей, но и спокойно, без мыслей о хлебе насущном, заниматься наукой. Здесь же он женился на дочери профессора греческого языка Мери Эверест, которая помогала Булю в работе и оставила после его смерти интересные воспоминания о своем муже; она стала матерью четырех дочерей Буля, одна из которых, Этель Лилиан Буль, в в замужестве Войнич, — автор популярного романа «Овод».

Первым попытался перевести законы мышления (формальную логику) из словесного царства, полного неопределенностей, в царство математики, был немецкий ученый Готфрид Вильгельм Лейбниц (в 1666 г.). Спустя более ста лет, в 1816 году, уже после смерти Лейбница, Джордж Буль подхватил его идею о создании логического универсального языка, подчиняющегося строгим математическим законам. Буль изобрел своеобразную алгебру – систему обозначений и правил, применимую ко всевозможным объектам, от чисел и букв, до предложений.

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

В 1848 году Джордж Буль опубликовал статью по началам математической логики – «Математический анализ логики, или Опыт исчисления Дедуктивных умозаключений», а в 1854 году появился главный его труд «Исследование законов мышления, на которых основаны математические теории логики и вероятностей». В этих работах отразилось убеждение Буля о возможности изучения свойств математических операций, осуществляемых не обязательно над числами. Ученый говорил о символическом методе, который он применял как к изучению дифференцирования и интегрирования, так и к логическому выводу и к теоретико-вероятностным рассуждениям. Именно он построил один из разделов формальной логики в виде некоторой «алгебры», аналогичной алгебре чисел, но не сводящейся к ней.

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

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

А еще несколько десятилетий спустя, уже в ХХ столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления (цифры которой 0 и 1 также подходят для описание двух состояний: утверждение истинно — утверждение ложно, лампочка горит — лампочка не горит), заложив тем самым основы для разработки цифрового электронного компьютера.

Список использованной литературы

Колмыкова, Е.А. Информатика [Текст]: учеб. пособие для студентов учреждений сред. проф. образования / Е.А. Колмыкова, И.А. Кумскова. – Москва: ИЦ «Академия», 2011. – 416 с. – [Допущено МО России].

Проектная деятельность учащихся [Текст] / Сост. Э. С. Ларина. — Волгоград: Изд-во «Учитель», 2009. – 155 с.

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания. Высказывания строятся над множеством , , , 0, 1>, где B — непустое множество, над элементами которого определены три операции:

отрицание (унарная операция), конъюнкция (бинарная), дизъюнкция (бинарная),

а также константы — логический ноль 0 и логическая единица 1.

Дизъю́нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например ). Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например ).

Аксиомы

1. , инволютивность отрицания, закон снятия двойного отрицания
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 

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

Простейшим и наиболее широко применяемым примером такой алгебраической системы является множество B, состоящее всего из двух элементов:

Как правило, в математических выражениях Ложь отождествляется с логическим нулём, а Истина — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать, что на данном множестве B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трёх выбранных операций.

Опираясь на этот математический инструментарий, логика высказываний изучает высказывания и предикаты. Также вводятся дополнительные операции, такие как эквивалентность («тогда и только тогда, когда»), импликация («следовательно»), сложение по модулю два («исключающее или»), штрих Шеффера , стрелка Пирса и другие.

Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция приобретает смысл вычитания из единицы; — немодульного сложения; & — умножения; — равенства; — в буквальном смысле сложения по модулю 2 (исключающее Или — XOR); — непревосходства суммы над 1 (то есть A B = (A + B) Свойства логических операций

1. Коммутативность: xy = yx, <&, >.
2. Идемпотентность: xx = x, <&, >.
3. Ассоциативность: (xy)z = x(yz), <&, >.
4. Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
5. ,
6. ,
7. .
8. Законы де Мо́ргана:
9. ,
10. .
11. Законы поглощения:
12. ,
13. .
14. Другие (1):
15. .
16. .
17. .
18. .
19. , инволютивность отрицания, закон снятия двойного отрицания.
20. Другие (2):
21. .
22. .
23. .
24. .
25. Другие (3) (Дополнение законов де Мо́ргана):
26. .
27. .

Существуют методы упрощения логической функции: например, Карта Карно, метод Куайна — Мак-Класки

История

Своим существованием наука «алгебра логики» обязана английскому математику Джорджу Булю, который исследовал логику высказываний. Первый в России курс по алгебре логики был прочитан П. С. Порецким в Казанском государственном университете.

Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями [1] . Чаще всего предполагается, что высказывания могут быть только истинными или ложными, то есть используется так называемая бинарная или двоичная логика, в отличие от, например, троичной логики.

Содержание

Определение [ править | править код ]

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания.

Высказывания строятся над множеством , ∧ <displaystyle land > , ∨ <displaystyle lor > , 0, 1>, где B — непустое множество, над элементами которого определены три операции:

а логический ноль 0 и логическая единица 1 — константы.

Так же используются названия

• Дизъю́нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например x 1 ∨ ¬ x 2 ∨ x 4 <displaystyle x_<1>lor
  eg x_<2>lor x_<4>>).
• Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например x 1 ∧ ¬ x 2 ∧ x 4 <displaystyle x_<1>land
  eg x_<2>land x_<4>>).

Унарная операция отрицания в тексте формул оформляется либо в виде значка перед операндом ( ¬ x <displaystyle lnot x> ) либо в виде черты над операндом ( x ¯ <displaystyle <ar >> ), что компактнее, но в целом менее заметно.

Аксиомы [ править | править код ]

1. x ¯ ¯ = x <displaystyle <ar <ar >>=x>, инволютивность отрицания, закон снятия двойного отрицания
2. x ∨ x ¯ = 1 <displaystyle xlor <ar >=1>
3. x ∨ 1 = 1 <displaystyle xlor 1=1>
4. x ∨ x = x <displaystyle xlor x=x>
5. x ∨ 0 = x <displaystyle xlor 0=x>
6. x ∧ x ¯ = 0 <displaystyle xland <ar >=0>
7. x ∧ x = x <displaystyle xland x=x>
8. x ∧ 0 = 0 <displaystyle xland 0=0>
9. x ∧ 1 = x <displaystyle xland 1=x>

Логические операции [ править | править код ]

Простейший и наиболее широко применяемый пример такой алгебраической системы строится с использованием множества B, состоящего всего из двух элементов:

Как правило, в математических выражениях Ложь отождествляется с логическим нулём, а Истина — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать, что на данном множестве B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трёх выбранных операций.

Опираясь на этот математический инструментарий, логика высказываний изучает высказывания и предикаты. Также вводятся дополнительные операции, такие как эквиваленция ↔ <displaystyle leftrightarrow > («тогда и только тогда, когда»), импликация → <displaystyle
ightarrow > («следовательно»), сложение по модулю два ⊕ <displaystyle oplus > («исключающее или»), штрих Шеффера ∣ <displaystyle mid > , стрелка Пирса ↓ <displaystyle downarrow > и другие.

Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция ¬ <displaystyle
eg > приобретает смысл вычитания из единицы; ∨ <displaystyle lor > — немодульного сложения; & — умножения; ↔ <displaystyle leftrightarrow > — равенства; ⊕ <displaystyle oplus > — в буквальном смысле сложения по модулю 2 (исключающее Или — XOR); ∣ <displaystyle mid > — непревосходства суммы над 1 (то есть A ∣ <displaystyle mid > B = (A + B) Свойства логических операций [ править | править код ]

1. Коммутативность: x ∘ y = y ∘ x , ∘ ∈ < ∧ , ∨ , ⊕ , ∼ , ∣ , ↓ ><displaystyle xcirc y=ycirc x,circ in <land ,lor ,oplus ,sim ,mid ,downarrow >>.
2. Идемпотентность: x ∘ x = x , ∘ ∈ < ∧ , ∨ ><displaystyle xcirc x=x,circ in <land ,lor >>.
3. Ассоциативность: ( x ∘ y ) ∘ z = x ∘ ( y ∘ z ) , ∘ ∈ < ∧ , ∨ , ⊕ , ∼ ><displaystyle (xcirc y)circ z=xcirc (ycirc z),circ in <land ,lor ,oplus ,sim >>.
4. Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
5. x ∧ ( y ∨ z ) = ( x ∧ y ) ∨ ( x ∧ z ) <displaystyle xland (ylor z)=(xland y)lor (xland z)>,
6. x ∨ ( y ∧ z ) = ( x ∨ y ) ∧ ( x ∨ z ) <displaystyle xlor (yland z)=(xlor y)land (xlor z)>,
7. x ∧ ( y ⊕ z ) = ( x ∧ y ) ⊕ ( x ∧ z ) <displaystyle xland (yoplus z)=(xland y)oplus (xland z)>.
8. Законы де Мо́ргана:
9. x ∧ y ¯ = x ¯ ∨ y ¯ <displaystyle <overline >=<ar >lor <ar >>,
10. x ∨ y ¯ = x ¯ ∧ y ¯ <displaystyle <overline >=<ar >land <ar >>.
11. Законы поглощения:
12. x ∧ ( x ∨ y ) = x <displaystyle xland (xlor y)=x>,
13. x ∨ ( x ∧ y ) = x <displaystyle xlor (xland y)=x>.
14. Другие (1):
15. x ∧ x ¯ = x ∧ 0 = x ⊕ x = 0 <displaystyle xland <ar >=xland 0=xoplus x=0>.
16. x ∨ x ¯ = x ∨ 1 = x ∼ x = x → x = 1 <displaystyle xlor <ar >=xlor 1=xsim x=x
    ightarrow x=1>.
17. x ∨ x = x ∧ x = x ∧ 1 = x ∨ 0 = x ⊕ 0 = x <displaystyle xlor x=xland x=xland 1=xlor 0=xoplus 0=x>.
18. x ⊕ 1 = x → 0 = x ∼ 0 = x ∣ x = x ↓ x = x ¯ <displaystyle xoplus 1=x
    ightarrow 0=xsim 0=xm >.
19. x ¯ ¯ = x <displaystyle <ar <ar >>=x>, инволютивность отрицания, закон снятия двойного отрицания.
20. Другие (2):
21. x ⊕ y = x ∧ y ¯ ∨ x ¯ ∧ y = ( x ∨ y ) ∧ ( x ¯ ∨ y ¯ ) <displaystyle xoplus y=xland <ar >lor <ar >land y=(xlor y)land (<ar >lor <ar >)>.
22. x ∼ y = x ⊕ y ¯ = 1 ⊕ x ⊕ y = x ∧ y ∨ x ¯ ∧ y ¯ = ( x ∨ y ¯ ) ∧ ( x ¯ ∨ y ) <displaystyle xsim y=<overline >=1oplus xoplus y=xland ylor <ar >land <ar >=(xlor <ar >)land (<ar >lor y)>.
23. x → y = x ¯ ∨ y = x ∧ y ⊕ x ⊕ 1 <displaystyle x
    ightarrow y=<ar >lor y=xland yoplus xoplus 1>.
24. x ∨ y = x ⊕ y ⊕ x ∧ y <displaystyle xlor y=xoplus yoplus xland y>.
25. Другие (3) (Дополнение законов де Мо́ргана):
26. x ∣ y = x ∧ y ¯ = x ¯ ∨ y ¯ <displaystyle xm >.
27. x ↓ y = x ∨ y ¯ = x ¯ ∧ y ¯ <displaystyle xdownarrow y=<overline >=<ar >land <ar >>.

Существуют методы упрощения логической функции: например, Карта Карно, метод Куайна — Мак-Класки

История [ править | править код ]

Своим существованием наука «алгебра логики» обязана английскому математику Джорджу Булю, который исследовал логику высказываний. Первый в России курс по алгебре логики был прочитан П. С. Порецким в Казанском государственном университете.

См. также [ править | править код ]

Примечания [ править | править код ]

1. ↑ Алгебра логики // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров . — 3-е изд. — М. : Советская энциклопедия, 1969—1978.

• Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное.

Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.

Высказывание — построение над множеством < B , ¬ , ∧ , ∨ , 0 , 1 ><displaystyle >
В — непустое множество, над элементами которого определены три базовые операции: конъюнкция ( ∧ <displaystyle land > или &, бинарная) • дизъюнкция ( ∨ <displaystyle lor > , бинарная) • отрицание ( ¬ <displaystyle
eg > , унарная)