Boolean algebra presentation discussion

[Erofivan]

Я бы сначала ввёл понятие логики не через lattice, а через примитивные утверждения. Например так:

Начало о логике как науке о правильных рассуждениях положил древнегреческий философ Аристотель (384 - 322 гг. до н. э.). А спустя две тысячи лет в 1847 г. Английский математик Джордж Буль (1815 - 1864 гг.) опубликовал статью "Математический анализ логики", которая, как принято считать, и положила начало новому разделу математики - логике.

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

Под высказыванием понимают повествовательное предложение, в отношении которого можно сказать, что оно истинно или ложно, Именно так объяснял понятие высказывания ещё Аристотель.

Почему это не определение? Да потому, что тогда пришлось бы ответить на вечный вопрос
«Что есть истина?» и на вопрос «Что такое ложь?». Попробуйте объяснить, и вы увидите, как это непросто.

Рассмотрим примеры:

Земля вращается вокруг солнца
Солнце вращается вокруг земли
Ленность при изучении дискретной математики приведёт к планетарной катастрофе
Прямоугольником называется четырёхугольник, у которого все углы прямые
Мысли материальны
Первое предложение, очевидно, является высказыванием, причём сегодня мы знаем, что оно истинно. Второе предложение тоже является высказыванием, причём ложным. Но это сегодня. А до Н. Коперника многие считали, что первое высказывание ложно, а второе истинно. Но и тогда это были высказывания, потому что в отношении каждого из них можно было утверждать, истинно оно или ложно. И логика тут ни при чём! Истинность или ложность утверждений устанавливает наука,
которая изучает соответствующие явления. Но заметьте, что второе высказывание отрицает первое и, следовательно, они не могут быть истинными одновременно. И это правило не зависит от смыслового содержания высказываний. Его можно сформулировать так: высказывание и его отрицание не могут быть одновременно истинными.
Это и есть один из первых законов логики, сформулированный ещё Аристотелем.

Вернёмся к нашим предложениям:

Истинно или ложно третье предложение, мы сегодня сказать не можем.
Тем не менее ясно, что в отношении него можно говорить истинно оно или ложно — катастрофа или наступит, или
нет. Значит, это тоже высказывание.

Четвертое предложение утверждением не является, так как это определение, введённое через уже известные понятия. И обсуждать истинность или ложность такого предложения нет никакого смысла
Пятое предложение тоже не является утверждением, ведь для начала нужно определить что такое "мысль". Каждый трактует его по-своему, и для одних мысль материальна, а для других нет.

После этого уже можно дать определение через lattice и оставить текущие слайды. Например сказав: а теперь, введём современное более формальное определение булевой алгебры, через недавно пройденные lattice.
И оставить 3 текущих примера

Потом после трёх примеров, мне кажется стоит дать список основных операций и как они обозначаются (базовые: коньюнкция, дизъюнкция, отрицания и вторичные: импликация, эквиваленция, xor), а также к ним таблицу истинности и что такое таблица истинности

Туда же бы ввести сразу понятие тождественной истины и лжи

После того, как дали несколько примеров, чтобы дать первичное понимание как составлять всякие высказывания (я бы дал высказывания, аля a & b or not c и к ним построил таблицу истинности. и так несколько примеров) можно дать уже всякие законы

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

После этого уже задаться вопросом, что до этого мы показали, что любой формулы, содержащей логические переменные можно построить таблицу истинности, но для любой ли таблицы истинности можно построить выражение?
Да, для любой
Можно, например, дать простой алгоритм (СКНФ или СДНФ). Например для таблицы FTFFTTFF

в таблице оставить только те строки, для которых значение логического выражения — это Истина;
в каждой клетке каждой такой строки заменить букву И на имя логической переменной, которая написана в заголовке этого столбца, а букву Л заменить на отрицание логической переменной, которая написана в заголовке этого столбца;
для каждой строки соединить знаком конъюнкции все записанные в клетках символы логических переменных и их отрицаний;
полученные символьные выражения соединить знаком дизъюнкции.
Понятно, что это уж совсем детский алгоритм, но я это тут написал для общей концепции. И затем дать в качестве примера таблицу истинности для который мы таким алгоритмом и составим выражение. Затем можно это же выражение сократить через выведенные в прошлых пунктах законы. У меня для этой таблицы получилось not (a and c) and b

Сейчас или до этого алгоритма дать понятие СКНФ и СДНФ и показать, что если бы у нас было больше истинных высказываний, чем ложных, то лучше было бы делать СКНФ.

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

После этого уже задаться вопросом, что до этого мы показали, что любой формулы, содержащей логические переменные можно построить таблицу истинности, но для любой ли таблицы истинности можно построить выражение?
Да, для любой
Можно, например, дать простой алгоритм (СКНФ или СДНФ). Например для таблицы FTFFTTFF

в таблице оставить только те строки, для которых значение логического выражения — это Истина;
в каждой клетке каждой такой строки заменить букву И на имя логической переменной, которая написана в заголовке этого столбца, а букву Л заменить на отрицание логической переменной, которая написана в заголовке этого столбца;
для каждой строки соединить знаком конъюнкции все записанные в клетках символы логических переменных и их отрицаний;
полученные символьные выражения соединить знаком дизъюнкции.
Понятно, что это уж совсем детский алгоритм, но я это тут написал для общей концепции. И затем дать в качестве примера таблицу истинности для который мы таким алгоритмом и составим выражение. Затем можно это же выражение сократить через выведенные в прошлых пунктах законы. У меня для этой таблицы получилось not (a and c) and b

Сейчас или до этого алгоритма дать понятие СКНФ и СДНФ и показать, что если бы у нас было больше истинных высказываний, чем ложных, то лучше было бы делать СКНФ.

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

И сейчас как раз ввести литерала, минтермы, макстермы, SoP PoS и атак далее

Затем ввести, что такое карты Карно и зачем они нужны. В Kenneth Rosen полно всяких картинок и упражнений - можно много взять оттуда

Вообще я бы дал после жегалки не BDD, а критерий Поста. Было бы прикольно рассмотреть его (возможно с доказтельством, но оно вроде в дз). С ним точно было ПОЛНО проблем в прошлом году и его плохо понимали и очень долго с ним мучались. Особенно со всеми 5-ю функциями и что они из себя представляют. У кт-шником есть прикольные примеры:
neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%B7%D0%B0%D0%B4%D0%B0%D0%BD%D0%B8%D0%B9_%D0%BF%D0%BE_%D0%94%D0%9C_2025_%D0%BE%D1%81%D0%B5%D0%BD%D1%8C

После этого уже дать BDD и ROBDD, но желательно сразу с примером и визуализацией, так как в интеренет долго искать и разбираться - особенно с ROBDD

И можно в соответстующие разделы или в конце презентации докинуть доп темы к соответсвующим топикам, например ANF Blake Scolem и так далее