Например, очень популярная задача алгебры логики — построение таблицы истинности. Давайте попробуем предположить, что нам может понадобиться, чтобы программа смогла это сделать?

А много нам и не надо

1. Нужен перебор логических переменных по совсем небольшому диапазону — от 0 до 1.
2. Правильно записанное логическое уравнение, чтобы проверить его при каждом наборе истины и лжи.

Вопрос встает только о конкретной реализации. Python — очень гибкий язык. Для разных формулировок задачи он может предложить разные инструменты, при использовании которых написание кода станет еще приятнее.

Начнем с обобщенной задачи — построение таблицы истинности. На этом примере можно показать, что математические операторы путают приоритет логических. Так что давайте составим таблицу истинности для уравнения A ≡ B ∧ C ⇒ A.

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

print("A B C")
for A in range(0, 2):
	for B in range(0, 2):
		for C in range(0, 2):
			result = A == ((B and C) <= A)
			print(A, B, C, result)
Вывод:
A B C
0 0 0 False
0 0 1 False
0 1 0 False
0 1 1 True
1 0 0 True
1 0 1 True
1 1 0 True
1 1 1 True

Мы заранее подписали каждый столбец, так что не запутаться в выводе будет проще.

Да, промежуточных результатов при такой реализации у нас нет. А зачем они нам? Нам важен итоговый результат — мы его получили.

У меня есть ощущение, что этот код не очень красивый. Он однозначно рабочий, но все-таки слишком много вложенных циклов. Как это можно решить?

В статье «Комбинаторика в информатике» мы обсуждали такую вещь, как модуль itertools, который содержит функции для работы с различными комбинациями. Как раз наш случай —

Сейчас нам пригодится функция product, которая создаст различные комбинации из указанных элементов. Изначально запишем их в отдельный массив для удобства:

from itertools import product
print("A B C")
d = [0, 1]
for i in product(d, repeat = 3):
	A, B, C = i
	result = A == ((B and C) <= A)
	print(A, B, C, result)
Вывод:
A B C
0 0 0 False
0 0 1 False
0 1 0 False
0 1 1 True
1 0 0 True
1 0 1 True
1 1 0 True
1 1 1 True

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

Пожалуй, стоит подробнее рассказать про строку:

Мы точно знаем, что i — это массив с 3 элементами, так как мы изначально задали создание наборов длиной 3. Если указать перед ним ровно столько же переменных, им можно присвоить соответствующие элементы массива в одну строку.

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

from itertools import product
print("A B C")
d = [0, 1]
for i in product(d, repeat = 3):
	A, B, C = i
	result = A == B and C <= A
	print(A, B, C, result)
Вывод:
A B C
0 0 0 True
0 0 1 False
0 1 0 False
0 1 1 False
1 0 0 False
1 0 1 False
1 1 0 True
1 1 1 True

Не вышло: итоговые значения таблиц истинности разные. Значит, приоритет действительно нарушается.

Другая наша возможная цель — проверить, будет ли выражение истинным всегда? Получим ли мы истину при любом наборе логических переменных?

Как и в прошлый раз, у нас есть не один вариант реализации. Будем анализировать выражение А ∧ (В ∨ С) ≡ В.

Первый вариант:

• перебор всех наборов — вложенными циклами или с помощью product;
• сохранение всех результатов уравнения от каждого набора;
• проверка, чтобы ни одно значение не было ложным — для сохранения всех результатов можно использовать список.

from itertools import product
d = [0, 1]
all_results = []
for i in product(d, repeat = 3):
	A, B, C = i
	result = (A and (B or C)) == B
	all_results.append(result)
if False not in all_results:
	print("Функция полностью истинна")
else:
	print("Функция истинна не всегда")
Вывод: Функция истинна не всегда

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

Второй вариант — функция all. Она возвращает True, если все значения внутри нее равны True — как раз наш случай. Чтобы записать программу максимально коротко, прямо внутри нее можно прописать и уравнение, и перебор его элементов:

from itertools import product
d = [0, 1]
result = all((A and (B or C)) == B for A, B, C in product(d, repeat = 3))
if result:
	print("Функция полностью истинна")
else:
	print("Функция истинна не всегда")

Здесь в переменную result записывается логическое значение True, если для всех наборов А, В, С из комбинаций d длиной 3 результат логического уравнения равен True. Если же среди всех результатов есть хоть один False — функция all даст нам False.

Для похожей задачи — чтобы не все значения уравнения были ложными — можно использовать функцию any.

from itertools import product
d = [0, 1]
result = any((A and (B or C)) == B for A, B, C in product(d, repeat = 3))
if result:
	print("Функция не всегда ложна")
else:
	print("Функция всегда ложна")
Вывод: Функция не всегда ложна

Python — гибкий язык. Если вам важнее видеть алгоритм работы кода более явно — используйте вложенные циклы, массивы для хранения значений и будьте более, чем на 100% уверены в каждом шаге. Если же вы хотите использовать дополнительные инструменты для сокращения объема кода и, как следствие, более быстрого его написания — вам в помощь комбинации product из itertools и инструменты массовой проверки all и any.

• Для импликации и эквиваленции в Python используются математические операторы сравнения, что немного нарушает их общий приоритет. Сохранить его можно с помощью скобок.
• Значения истины и лжи в Python являются логическим типом данных, который может принимать значение True или False и соответствует 1 и 0.
• Функция all проверяет, все ли переданные ей значения истинны. Функция any проверяет, есть ли среди всех переданных значений хоть одно истинное.

Задание 1.
Для выражения А ∨ В ∧ ¬(В ∧ А) выберите верную запись на языке Python (с сохранением порядка действий):

1. A and B or not B or A
2. A and B or not (B or A)
3. A or B and not B and A
4. A or B and not (B and A)

Задание 2.
Для выражения ¬А ⇒ В ≡ А ∧ В выберите верную запись на языке Python (с сохранением порядка действий):

1. not (А <= В == А and В)
2. not А <= В == (А and В)
3. ((not A) <=  B) == (A and B)
4. (not А) <= (В == (А and В))

Задание 3.
Чему будет равен последний столбец таблицы истинности для уравнения: 
A ∧ B ⇒ C ∧ D ∨ D ∧ A?

1. 11101101
2. 11101111
3. 00000011
4. 11000111

Задание 4.
Выберите уравнение, которое во всех случаях принимает значение истины:

1. ¬(A ∧ B) ∧ ¬(C ∧ ¬A)
2. ¬(A ∧ B) ∨ ¬(C ∧ ¬A)
3. A ∧ B ∧ ¬(C ∧ ¬A)
4. ¬(A ∧ B) ∨ ¬(C ∧ A)

Ответ: 1. — 4; 2. — 3; 3. — 1; 4. — 2.

Математическая логика. Логика использовалась для тысяч… | Брэндон Скеррит | Заметки о компьютерных науках

Логика использовалась на протяжении тысячелетий, от философии до математики, а теперь и до искусственного интеллекта. Логика связана с истинностью и ложностью утверждений. Логика, которую мы будем изучать, будет отвечать на вопрос: «когда утверждение следует из набора утверждений?»

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

Предложения могут быть только истинными или ложными.

Интерпретация присваивает пропозициональному утверждению истинностное значение Истина или Ложь. True или False могут быть представлены как 0 и 1 соответственно.

Существует около 500 000 способов представления логических символов, вот наиболее распространенные способы

Символ в логике 9или И или ,

Символ в электронике

Что он делает

Принимает >1 входных данных, и если оба входных значения истинны, выдает истинные значения.

Правда Таблица

Символ в логике

В, или, «или»

Символ в электронике

Что он делает

. чем вывод верен.

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

Символ в логике <=> или ≡

Символ в электронике Нет, это концепция, а не ворота.

Что он делает A и B должны принимать одно и то же значение истинности

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

A B A <=> B 1 1 = 1 0 1 = 0 1 0 = 0 0 0 = 1

05 Логика => или «если a, то b»

Символ в электронике Нет

Что делает Если A верно, то верно и B

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

Имея интерпретацию I, мы можем вычислить истинностное значение любой формулы P при I. То есть, учитывая версию формулы, мы можем вычислить истинностное значение.

если I(P) = 1, то мы говорим, что P истинно при интерпретации I. если I(P) = 0, то мы говорим, что P ложно при интерпретации I.

Этот раздел может помочь читателю разобраться в логических головоломках. .

На острове есть два типа жителей: рыцари, которые всегда говорят правду, и лжецы, которые всегда лгут. Вы отправляетесь на остров и встречаете А и Б. А говорит, что «Б — рыцарь» Б говорит, что «Мы двое противоположных типов»

Что такое А и Б?

Итак, у нас есть 2 варианта, р: «А — рыцарь»; и q: «B — рыцарь»

У нас есть 2 варианта, потому что один из них должен быть рыцарем. Либо и A, и B — лжецы, что делает B рыцарем, поскольку он сказал правду, значит, он солгал, либо A — рыцарь и говорит правду, что B — рыцарь.

Варианты для лица A p истинно, то есть утверждение «A — рыцарь» истинно. P => Q p ложно, то есть утверждение «A — рыцарь» ложно. ¬P => ¬Q

Варианты для человека B q верно, тогда q => ¬p q ложно, тогда ¬q => ¬p

Теперь нам просто нужно построить таблицу истинности для этих значений

p q ¬p ¬q p => q ¬p => ¬q q => ¬p ¬q => ¬p 0 0 1 1 1 1 1 1 = 1

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

Примечание. Слайды лекций для этого не помогли, и для этого нет звука. Пожалуйста, напишите мне, что это такое.

Современные компьютеры используют для работы логические вентили. Вы должны иметь представление о логических элементах из приведенного выше.

Никогда не объединяйте два входных провода

Если есть 2 отдельных входа, A и B, вы не можете объединить их в один провод.

Один входной провод можно разделить на части и использовать как вход для двух отдельных ворот

Если у вас есть один вход A, его можно разделить на 2 отдельных провода.

Выходной провод можно использовать как вход

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

Ни один выход логического элемента не может в конечном счете вернуться к этому логическому элементу.

Имея таблицу, подобную приведенной ниже, как бы мы построили для нее логическую схему?

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

Две схемы эквивалентны, если они производят одинаковый результат при одинаковых входных данных.

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

Символ «≡» используется для обозначения отношения эквивалентности.

Факты

≡ рефлексивно ≡ транзитивно ≡ симметрично

Есть несколько правил, которые мы можем использовать для упрощения пропозициональных формул.

Коммуникативное право

AB = BA, A + B = B + A

Примеры: 6 * 2 = 12 и 2 * 6 = 12 3 + 4 = 7 и 4 + 3 = 7

Ассоциативный закон

2 + 4) + 5 = 6 + 5 = 11 2 + (4 + 5) = 2 + 9 = 11

Распределительный закон

a(b+c) = ab + ac

Пример: 3 × ( 2 + 4) = 3 * 6 = 18 3 × 2 + 3 × 4 = 6 + 12 = 18

Законы Деморгана

(A ∪ B)’ = (A)’ ∩ (B)’ Первый закон гласит, что дополнением объединения двух множеств является пересечение дополнений.

(A ∩ B)’ = (A)’ ∪ (B)’ Второй закон гласит, что дополнение пересечения двух множеств есть объединение дополнений.

Чтобы получить хороший пост в блоге о понимании этих законов, нажмите (здесь)[https://brilliant. org/wiki/de-morgans-laws/]

Прочие правила

Not Not A = A A или A и B = A A или не A и B = A и B (A или B) (A или C) = A или B и C

Что делать дальше С этого момента превратите схему в логическое выражение и упростите ее используя приведенные выше правила. 9, v или ¬.

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

Символ в логике

Нет

Символ в электронике

Что он делает

Логический элемент XOR принимает >1 вход и выполняет исключительную дизъюнктуру. Выход вентиля XOR истинен только в том случае, если один из его входов отличается от другого входа.

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

Символ в логике

Нет

Символ в электронике

Что он делает

Логический элемент И-НЕ принимает >1 входов, а выход противоположен вентилю И. Вывод истинен, когда один или несколько, но не все входные данные ложны.

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

Все логические функции могут быть созданы с использованием вентилей XOR или NAND.

Двоичная система счисления, состоящая из 0 и 1.

Преобразование десятичного числа в двоичное

В качестве альтернативы вы можете запомнить степени 2. 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024… А затем, чтобы преобразовать число в двоичное, давайте скажем, 6, вы строите это из разных сил. Итак, 6 — это 011, а затем переверните это, 110

Двоичное сложение

Кое-что, что вам нужно знать о двоичном коде 0 + 0 = 0 1 + 0 = 1 0 + 1 = 1 1 + 1 = 10

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

011

полусумматор

полусумматор — это тип двоичного сумматора в электронике, который складывает два одиночных двоичных разряда и обеспечивает выход плюс значение переноса.

Примечание. Полусумматор Бориса слишком сложен, вы можете добиться того же, заменив 3 его логических элемента одним элементом XOR.

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

Полный сумматор

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

Посмотрите это видео для лучшего понимания

Обозначение черного ящика

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

4-битный сумматор

Используя нотацию черного ящика, мы можем создать 4-битный сумматор

http://www.electronics-tutorials.ws/combination/comb_7.html

Компьютерное представление отрицательных целых чисел

966 Для представления целых чисел используется фиксированное количество битов: 8, 16, 32 или 64 бита. Беззнаковое целое может занимать все доступное пространство.

Вы можете «подписать» двоичное число, чтобы указать, отрицательное оно или нет. Например, число 10 может быть представлено в 8-битном виде как 00001010, а -10 может быть представлено в 8-битном виде как 10001010

. Но иногда это вызывает проблемы, например, 10000000 представляет -0. Чтооо?? Отрицательный 0? Да! Это верно, и это именно та проблема, которую это вызывает.

Здесь в игру вступает дополнение 2.

Дополнение до двух

Преобразование десятичной дроби в дополнение до двух

1) Преобразовать число в двоичное, игнорируя пока знак. Таким образом, 5 — это 0101, а -5 — это 0101.

2) Если число положительное, то все готово, дальше ничего не нужно. Иначе…

3) Если число отрицательное, то:

• Найдите дополнение (например, преобразуйте все 0 в 1 и все 1 в 0)
• Добавьте 1 к дополнению

Итак, инвертируйте все цифры и добавьте 1 . Простой.

Если вы хотите узнать, почему это работает, нажмите здесь

Сложение в двоичном виде, пересмотренный вариант

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

Вычитание в двоичном формате

Рассматривайте это как сложение, но отрицайте второй операнд. Таким образом, 4–3 — это просто 4 + (-3)

, что равно

0100

Переполнение

Примером этого является 4 + 7

0100

Правильный результат 9 слишком велик для 4-битного представления.

Если оба входа в дополнение имеют одинаковый знак, а выходной знак отличается, произошло переполнение.

Переполнение не может произойти, если знаки различаются.

Первоначально опубликовано по адресу brandonskerritt.github.io 25 ноября 2017 г.

Почему логика важна для информатики и математики