Символ f обозначено логическое выражение от трех аргументов x y z: Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, У, Z….
Таблица истинности онлайн
Назначение сервиса. Онлайн-калькулятор предназначен для построения таблицы истинности для логического выражения.
Таблица истинности – таблица содержащая все возможные комбинации входных переменных и соответствующее им значения на выходе.
Таблица истинности содержит 2n строк, где n – число входных переменных, и n+m – столбцы, где m – выходные переменные.
Решение онлайн
Видеоинструкция
Инструкция. При вводе с клавиатуры используйте следующие обозначения:
Клавиша
Оператор
!
¬
Отрицание (НЕ)
|
|
Штрих Шеффера (И-НЕ)
#
↓
Стрелка Пирса (ИЛИ-НЕ)
*
&
Конъюнкция (И)
+
v
Дизъюнкция (ИЛИ)
^
⊕
Исключающее ИЛИ, сумма по модулю 2 (XOR)
@
→
Импликация (ЕСЛИ-ТО)
%
←
Обратная импликация
=
≡ (~, ↔)
Эквивалентность (РАВНО)
Логическое выражение:
Вывод промежуточных таблиц для таблицы истинности
Построение СКНФ
Построение СДНФ
Построение полинома Жегалкина
Построение карты Вейча-Карно
Минимизация булевой функции методом Квайна
Например, логическое выражение abc+ab~c+a~bc необходимо ввести так: a*b*c+a*b=c+a=b*c Для ввода данных в виде логической схемы используйте этот сервис. y).
Максимальное количество переменных равно 10.
Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики — алгебры логики. В алгебре логики можно выделить три основные логические функции: «НЕ» (отрицание), «И» (конъюнкция), «ИЛИ» (дизъюнкция).
Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики.
Функция алгебры логики называется полностью определённой если заданы все 2n её значения, где n – число выходных переменных.
Если определены не все значения, функция называется частично определённой.
Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики.
Для представления функции алгебры логики используется следующие способы:
словесное описание – это форма, которая используется на начальном этапе проектирования имеет условное представление.
описание функции алгебры логики в виде таблицы истинности.
описание функции алгебры логики в виде алгебраического выражения: используется две алгебраические формы ФАЛ:
а) ДНФ – дизъюнктивная нормальная форма – это логическая сумма элементарных логических произведений. ДНФ получается из таблицы истинности по следующему алгоритму или правилу:
1) в таблице выбираются те строки переменных для которых функция на выходе =1.
2) для каждой строки переменных записывается логическое произведение; причём переменные =0 записываются с инверсией.
3) полученное произведение логически суммируется.
Fднф= X1*Х2*Х3 ∨ Х1x2Х3 ∨ Х1Х2x3 ∨ Х1Х2Х3 ДНФ называется совершенной, если все переменные имеют одинаковый ранг или порядок, т.е. в каждое произведение обязательно должны включаться все переменные в прямом или инверсном виде. б) КНФ – конъюнктивная нормальна форма – это логическое произведение элементарных логических сумм.
КНФ может быть получена из таблицы истинности по следующему алгоритму:
1) выбираем наборы переменных для которых функция на выходе =0 2) для каждого набора переменных записываем элементарную логическую сумму, причём переменные =1 записываются с инверсией.
3) логически перемножаются полученные суммы.
Fскнф=(X1 V X2 V X3) ∧ (X1 V X2 V X3) ∧ (X1 V X2 V X3) ∧ (X1 V X2 V X3)
КНФ называется совершенной, если все переменные имеют одинаковый ранг.
По алгебраической форме можно построить схему логического устройства, используя логические элементы.
Рисунок1- Схема логического устройства
Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможных логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2N строк, так как существует 2N различных комбинаций возможных значений аргументов.
Операция НЕ — логическое отрицание (инверсия)
Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:
если исходное выражение истинно, то результат его отрицания будет ложным;
если исходное выражение ложно, то результат его отрицания будет истинным.
Для операции отрицания НЕ приняты следующие условные обозначения:
не А, Ā, not A, ¬А, !A
Результат операции отрицания НЕ определяется следующей таблицей истинности:
A
не А
0
1
1
0
Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот.
Операция ИЛИ — логическое сложение (дизъюнкция, объединение)
Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами. Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений.
Применяемые обозначения: А или В, А V В, A or B, A||B.
Результат операции ИЛИ определяется следующей таблицей истинности:
A
B
А или B
0
0
0
0
1
1
1
0
1
1
1
1
Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В — ложны.
Операция И — логическое умножение (конъюнкция)
Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение. Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения.
Применяемые обозначения: А и В, А Λ В, A & B, A and B.
Результат операции И определяется следующей таблицей истинности:
A
B
А и B
0
0
0
0
1
0
1
0
0
1
1
1
Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях.
Операция «ЕСЛИ-ТО» — логическое следование (импликация)
Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием из этого условия.
Применяемые обозначения:
если А, то В; А влечет В; if A then В; А→ В.
Таблица истинности:
A
B
А → B
0
0
1
0
1
1
1
0
0
1
1
1
Результат операции следования (импликации) ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.
Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)
Применяемое обозначение: А ↔ В, А ~ В.
Таблица истинности:
A
B
А↔B
0
0
1
0
1
0
1
0
0
1
1
1
Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.
Операция «Сложение по модулю 2» (XOR,
исключающее или, строгая дизъюнкция)
Применяемое обозначение: А XOR В, А ⊕ В.
Таблица истинности:
A
B
А⊕B
0
0
0
0
1
1
1
0
1
1
1
0
Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.
Приоритет логических операций
Действия в скобках
Инверсия
Конъюнкция ( & )
Дизъюнкция ( V ), Исключающее ИЛИ (XOR), сумма по модулю 2
Импликация ( → )
Эквивалентность ( ↔ )
Совершенная дизъюнктивная нормальная форма
Совершенная дизъюнктивная нормальная форма формулы (СДНФ) это равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций, обладающая свойствами:
Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x1,x2,…xn).
Все логические слагаемые формулы различны.
Ни одно логическое слагаемое не содержит переменную и её отрицание.
Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.
СДНФ можно получить или с помощью таблиц истинности или с помощью равносильных преобразований. Для каждой функции СДНФ и СКНФ определены единственным образом с точностью до перестановки.
Совершенная конъюнктивная нормальная форма
Совершенная конъюнктивная нормальная форма формулы (СКНФ) это равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций, удовлетворяющая свойствам:
Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x1,x2,…xn).
Все элементарные дизъюнкции различны.
Каждая элементарная дизъюнкция содержит переменную один раз.
Ни одна элементарная дизъюнкция не содержит переменную и её отрицание.
1.1 Логические операции
Математика обычно включает в себя объединение истинных (или гипотетически истинных)
утверждения различными способами для получения (или доказательства) новых истинных утверждений.
Начнем с разъяснения некоторых из этих фундаментальных идей.
Под предложением мы подразумеваем
утверждение, имеющее определенное истинностное значение ,
истина (T) или ложь (F) — например,
«В 1492 году Колумб плыл по синему океану». (T)
«Наполеон выиграл битву при Ватерлоо». (Ф)
92+y = 12$», то $P(2,8)$ и $P(3,3)$
верно, а $P(1,4)$ и $P(0,6)$ ложны. Если $Q(x,y,z)$ равно «$x+y
Является ли предложение истинным или ложным, обычно зависит от того, что мы
говорят о том, что одно и то же предложение может быть истинным или ложным в зависимости от
по контексту; например, формула $x|y$ означает, что `$x$ делит
$у$’. То есть $x|y$, если существует некоторый $z$ такой, что $y=x\cdot z$. Сейчас,
правда ли, что $3|2$? Это зависит: если мы говорим о целых числах,
ответ — нет; если мы говорим о рациональных числах, то ответ
да, потому что $2=3\cdot(2/3)$. (Конечно, если $x\not=0$ и $y$ любых рациональных чисел, затем $x|y$, так что это не очень
полезное понятие. При обычном использовании внешний вид формулы
«$x|y$» подразумевает , что $x$ и $y$ являются целыми числами.)
Вселенная дискурса для конкретной области математики представляет собой набор, который
содержит все, что представляет интерес для этой темы. Когда мы
изучение математических формул типа «$x$ делит $y$» на переменные
предполагается, что они принимают значения в любом дискурсивном универсуме
подходит для конкретного предмета. Вселенная дискурса
обычно ясно из обсуждения, но иногда нам нужно будет
идентифицируйте его явно для ясности.
Вселенная дискурса обычно обозначается $U$.
Сложные предложения и формулы составляются из более простых,
используя небольшое количество логических операций . Просто горстка
этих операций позволит нам сказать все, что мы должны сказать в
математика.
Если $P$ — это формула, то «не $P$» — это другая формула.
формула, которую мы символически запишем как $\lnot P$. Конечно, $\lне
P$ ложно, если $P$ истинно, и наоборот, например,
«6 не является простым числом» или «Неверно, что 6
премьер» или
«$\lnot(\hbox{6 простое число})$» (T)
«Рональд Рейган не был президентом». (Ф)
Предположим, что $P$ и $Q$ — формулы. Затем
«$P$ и $Q$» — это формула, записанная символически
как $P\land Q$, называемое соединением из $P$ и $Q$. Чтобы $P\land Q$ были истинными как $P$, так и $Q$
должно быть истинным, иначе оно ложно, например,
«5 долларов = 6 долларов и 7 долларов = 8 долларов». (F)
«Сиэтл находится в Вашингтоне, а Бойсе — в Айдахо». (T)
«Толстой был русским, а Диккенс был
Французский.» (Ф)
Если $P$ и $Q$ являются формулами, то формула «$P$ или $Q$» записывается символически как $P\lor Q$, называемая дизъюнкция $P$ и $Q$. Это
важно отметить, что это включительно или, то есть, «либо
или оба». Итак, если $P$, $Q$ или оба $P$ и $Q$ верны,
то же самое и с $P\lor Q$. Единственный случай, когда $P\lor Q$ может быть ложным, состоит в том, что оба $P$
и $Q$ ложны, например,
«Вашингтон в Канаде или Лондон в Англии». (T)
«$5
«Ленин был испанцем или Ганди был итальянцем». (Ф)
Если $P$ и $Q$ — формулы, то «если $P$, то $Q$»
или «$P$ означает, что $Q$» написано
$P\подразумевает Q$, используя условное обозначение ,
$\подразумевает$. Не очевидно (по крайней мере, для большинства людей), под чем
обстоятельства $P\имеет Q$ должно быть правдой. Отчасти это потому, что
«if… then» используется в обычном английском языке более чем одним способом, однако
нам нужно исправить правило, которое позволит нам точно знать, когда $P\ подразумевает
Q$ верно. Конечно, если $P$ истинно, а $Q$ ложно, $P$ не может
подразумевают $Q$, поэтому $P\implis Q$ в этом случае ложно. Чтобы помочь нам с
в других случаях рассмотрим следующее утверждение:
«Если $x$ меньше 2, то $x$ меньше 4».
Это утверждение должно быть верным независимо от значения $x$.
(при условии, что вселенная дискурса является чем-то знакомым, например
целые числа). Если $x$ равно 1, оно оценивается как $\rm T\имплицитно T$, если $x$
равно 3, оно становится $\rm F\implis T$, а если $x$ равно 5, становится
$\rm F\ подразумевает F$. Таким образом, оказывается, что $P\implis Q$ истинно, если только
$P$ истинно, а $Q$ ложно. Это правило, которое мы принимаем.
Наконец, biconditional , написанный $\Leftrightarrow$, соответствует
фраза «если и только если» или «если»
для краткости. Таким образом, $P \Leftrightarrow Q$ истинно, когда и $P$, и $Q$
имеют одинаковое истинностное значение, иначе оно ложно.
Пример 1.1.2 Предположим, что $P(x,y)$ равно «$x+y=2$» и $Q(x,y)$
равно «$xy>1$». Тогда, когда $x=1$ и $y=1$,
$\lnot P(x,y)$, $P(x,y)\land Q(x,y)$, $P(x,y)\lor Q(x,y)$,
$P(x,y)\имеет Q(x,y)$ и $P(x,y)\Leftrightarrow Q(x,y)$
имеют значения истинности F, F, T, F, F соответственно, а когда
$x=2$ и $y=3$ имеют истинностные значения
Т, Ф, Т, Т, Ф соответственно.
$\квадрат$
Используя операции $\lnot$, $\land$, $\lor$, $\implies$,
$\Leftrightarrow$, мы можем построить составных выражений, таких как
$$
(P\land (\lnot Q))\ подразумевает ((\lnot R)\lor ((\lnot P)\land Q)).
$$
Как показывает этот пример, иногда необходимо
включать много круглых скобок, чтобы группировать термины
в формуле ясно. Как и в алгебре, где
умножение имеет приоритет перед сложением, мы можем
убрать некоторые скобки
согласование определенного порядка, в котором логически
операции выполняются. Мы
будет применять операции в этом порядке, начиная с
от первого к последнему: $\lnot$, $\land$, $\lor$, $\implies$
и $\Leftrightarrow$. Так
$$A\подразумевает B\или C\land\lnot D
$$
сокращение от
$$A\подразумевает (B\или (C\land (\lnot D))).
$$
Как и в алгебре, часто разумно включать
несколько дополнительных скобок, чтобы убедиться, что предполагаемый смысл понятен.
Большая часть информации, которую мы обсудили, может быть резюмирована в таблицы истинности . Например, таблица истинности для
$\lnot P$:
$P$
$\lnot P$
Т
Ф
Ф
Т
В этой таблице две строки, потому что есть только две возможности для
истинное значение $P$. Другие логические операции используют две переменные, поэтому
им требуется 4 строки в их таблицах истинности.
$P$
$Q$
$P\land Q$
$P\lor Q$
$P\Rightarrow Q$
$P\Leftrightarrow Q$
Т
Т
Т
Т
Т
Т
Ф
Т
Ф
Т
Т
Ф
Т
Ж
Ж
Т
Ж
Ж
Ж
Ж
Ж
Ж 9п$
строки в таблице, потому что есть много разных способов назначить
T и F для $n$ простых формул в составном выражении. Таблица истинности для $(P\land Q)\lor \lnot R$ такова:
$P$
$Q$
$R$
$P \land Q$
$\lnot R$
$(P \land Q)\lor\lnot R$
Т
Т
Т
Т
Ф
Т
Ф
Т
Т
Ф
Ф
Ф
Т
Ф
Т
Ф
Ф
Ф
Ф
Ф
Т
Ф
Ф
Ф
Т
Т
Ф
Т
Т
Т
Ф
Т
Ф
Ф
Т
Т
Т
Ф
Ф
Ф
Т
Т
Ф
Ф
Ф
Ф
Т
Т
Обратите внимание, как включение промежуточных шагов облегчает работу с таблицей. посчитай и прочитай.
Тавтология — это логическое выражение, которое
всегда оценивается как T, то есть последний столбец его таблицы истинности
состоит только из Т. Иногда говорят, что тавтология равна 9.0005 действительный ; хотя «действительный» используется в других контекстах как
ну, это не должно вызывать путаницы. Например, $(P\land Q)\lor
P\Leftrightarrow P$ является тавтологией, поскольку ее таблица истинности такова:
$P$
$Q$
$P\land Q$
$(P\land Q)\lor P$
$(P\land Q)\lor P\Leftrightarrow P$
Т
Т
Т
Т
Т
Ф
Т
Ф
Ф
Т
Т
Ж
Ж
Т
Т
Ф
Ф
Ф
Ф
Т
Мы перечисляем несколько важных тавтологий в следующей теореме.
Доказательство. Доказательства оставлены в качестве упражнений.
$\qed$
Заметим, что (b) и (c) — коммутативные законы, (d) и (e) —
ассоциативные законы и (е) и (ж) говорят, что $\land$
и $\lor$ распределяются друг над другом. Это говорит о том, что существует
форма алгебры для логических выражений, аналогичная алгебре
для числовых выражений. Этот предмет называется Булева алгебра и имеет множество применений.
особенно в информатике.
Если две формулы всегда принимают одно и то же истинностное значение независимо от того,
элементы из вселенной дискурса, которые мы заменяем различными
переменные, то мы говорим, что они эквивалентны . Стоимость эквивалента
формулы в том, что они говорят одно и то же. Это всегда правильный шаг
в доказательстве заменить некоторую формулу эквивалентной. Кроме того,
многие тавтологии содержат важные идеи для построения доказательств. Для
например, (k) говорит, что если вы хотите показать, что $P\Leftrightarrow Q$, это
можно (и часто целесообразно) разбить доказательство на два
части, одна из которых доказывает импликацию $P\implis Q$, а вторая
доказывая обратное , $Q\подразумевает P$.
При чтении теоремы 1.1.3 у вас может возникнуть
заметил, что $\land$ и $\lor$ обладают многими схожими свойствами. Они называются «двойственными» понятиями — для любого свойства
один, есть почти идентичное свойство, которому удовлетворяет другой,
экземпляры двух операций поменялись местами. Это часто
означает, что когда мы доказываем результат, включающий одно понятие, мы получаем
соответствующий результат для своего двойственного без дополнительной работы.
Джордж Буль. Буль
(1815–1864) имел только обычное школьное образование, хотя и выучил
Греческий и латынь самостоятельно. Он начал свою карьеру в качестве элементарного
школьным учителем, но решил, что ему нужно больше узнать о
математики, поэтому он начал изучать математику, а также
языки, необходимые ему для чтения современной литературы на
математика. В 1847 году он опубликовал короткую книгу «Математический анализ».
Анализ логики , который, можно справедливо сказать, лег в основу исследования.
математической логики. Ключевой вклад работы заключался в
переопределить «математику» так, чтобы она означала не просто «изучение чисел и
величина», но изучение символов и манипулирование ими в соответствии с
к определенным правилам. Важность этого уровня абстракции для
будущее математики трудно переоценить. Вероятно, на
Благодаря этой работе он перешел на должность в Куинс-колледж в Корке.
В «Исследовании законов мысли» , опубликованном в 1854 г.,
Буль установил настоящую формальную логику, развивая то, что сегодня называется
Булева алгебра или иногда алгебра множеств . Он использовал символы для
сложение и умножение как операторы, но в совершенно абстрактном
смысл. Сегодня эти символы все еще иногда используются в булевых выражениях.
алгебре, хотя символы `$\land$’ и `$\lor$’, и `$\cap$’ и
`$\cup$’ также используются. Буль применил алгебраическую манипуляцию к
процесс рассуждения. Вот простой пример типа
манипуляцию, которую он проделал: уравнение $xy=x$ (которое сегодня можно было бы записать
$x\land y = x$ или $x\cap y = x$) означает, что «все вещи, удовлетворяющие
$x$ удовлетворяет $y$’, или, говоря нашим языком, $x\имеет y$. Если также $yz=y$ (что
есть $y\implis z$), то подстановка $y=yz$ в $xy=x$ дает
$x(yz)=x$ или $(xy)z=x$. Заменив $xy$ на $x$, получим $xz=x$, или
$x\подразумевает z$. Этот простой пример логического рассуждения используется более
и далее по математике.
92+bD+c=0$, обработка
$D$ как номер , предоставляет информацию о решениях для
дифференциальное уравнение.
Информация здесь взята из A History of Mathematics, by
Карл Б. Бойер, Нью-Йорк: John Wiley and Sons, 1968. Подробнее
информацию см. Лекции о десяти британских математиках , автор
Александр Макфарлейн, Нью-Йорк: John Wiley & Sons, 1916.
Пример 1.1.1 Постройте таблицы истинности для следующих логических выражений:
а) $(P\land Q)\или \lnot P$
б) $P\имеет (Q\land P)$
c) $(P\land Q)\Стрелка влево (P\lor \lnot R)$
d) $\lnot P\имеет в виду \lnot(Q\lor R)$
Пример 1.1.2 Проверьте тавтологии в теореме 1.1.3.
Пример 1.1.3 Предположим, что $P(x,y)$ — это формула «$x+y=4$», а $Q(x,y)$ — это
формула «$x
а) Найти таблицы истинности для
$$
P\land (\lnot Q)\land R, \quad\quad (\lnot P)\land Q\land (\lnot R)
$$
b) Используйте их, чтобы найти таблицу истинности для
$$
(P\land (\lnot Q)\land R)\lor ((\lnot P)\land Q\land (\lnot R))
$$
c) Используйте метод, предложенный частями (a) и (b)
найти формулу со следующей таблицей истинности.
$P$
$Q$
$R$
???
Т
Т
Т
Т
Ф
Т
Т
Ф
Т
Ж
Т
Ж
Ф
Ф
Т 9009n$ T и F — это
последний столбец таблицы истинности для некоторой формулы из $n$ букв.
Пример 1.1.5 Если $P_1, P_2,\ldots, P_n$ — это список из $n$ формул,
максимальное количество составных формул, использующих этот список, может быть построено,
никакие два из которых не эквивалентны?
CSE 341 — Основы схемы
CSE 341 — Основы схемы
Схема профиля
диалект Лиспа
в основном функциональные (но не чисто функциональные)
динамическая типизация; безопасный тип
исключительно хранилище на основе кучи с GC
передача по значению с семантикой указателя
с лексической областью видимости (изначально Lisp использовал динамическую область видимости)
первоклассные функции
анонимные функции
синтаксически простой, правильный (но много скобок)
все по спискам!
эквивалентность данных программы (это делает
легко писать программы Scheme, которые обрабатывают/производят другие
программы, напр. компиляторы, редакторы структур, отладчики и т.д.)
, как правило, может быть запущен как интерпретированный, так и скомпилированный
Лисп был разработан в конце 50-х Джоном Маккарти. Диалект Схемы был
разработан Гаем Стилом и Джерри Суссманом в середине 70-х. В 80-е годы
Был разработан стандарт Common Lisp. Common Lisp — это язык кухонной раковины:
много много особенностей.
Типы данных и операции примитивной схемы
Некоторые примитивные ( atomic ) типы данных:
номеров
целых чисел (примеры: 1, 4, -3, 0)
реалов (примеры: 0,0, 3,5, 1,23E+10)
рациональные числа (например, 2/3, 5/2)
символов (например, fred, x, a12, набор!)
логическое значение: схема использует специальные символы #f и #t для представления ложного и
истинный.
строк (например, «привет, матрос»)
символы (например, #\c)
Регистр обычно не имеет значения (за исключением символов или строк). Примечание
что у вас могут быть забавные символы, такие как + или — или ! в центре
символы. (Однако у вас не может быть скобок.) Вот некоторые из основных
операторы, предусмотренные этой схемой для указанных выше типов данных.
Арифметические операторы (+, -, *, /,
абс, кврт)
Относительный (=, <, >, <=, >=) (для чисел)
Относительный (eqv?, равный?) для произвольных данных
(подробнее об этом позже)
Логические (и, или, нет): и и
или являются логическими операторами короткого замыкания.
Некоторые операторы являются предикатами , то есть являются тестами на истинность.
В Scheme они возвращают #f или #t. Особенность: в MIT Scheme
пустой список эквивалентен #f, а #f печатается как (). Но хорошо
стиль заключается в том, чтобы писать #t или #f всякий раз, когда вы имеете в виду истину или ложь, и
write(), когда вы действительно имеете в виду пустой список. См. также «Булево
Особенности» ниже.
Итак, мы знаем имена нескольких операторов. Как мы их используем?
Схема предоставляет нам единый синтаксис для вызова функций:
(функция arg1 arg2 ... argN)
Это означает, что все операторы, включая арифметические, имеют
Синтаксис префикса . Аргументы передаются по значению (кроме специальные формы , обсуждаемые позже, позволяющие использовать такие приятные вещи, как
короткое замыкание).
Примеры:
(+ 2 3)
(абс -4)
(+ (* 2 3) 8)
(+ 3 4 5 1)
;; обратите внимание, что + и * могут принимать произвольное количество аргументов
;; на самом деле так может - и/но у вас голова закружится, пытаясь вспомнить
;; что это значит
;;
;; точка с запятой означает, что остальная часть строки является комментарием
Тип данных списка
Возможно, самым важным встроенным типом данных в Scheme является
список. В Scheme списки не ограничены, возможно, неоднородны.
коллекции данных. Примеры:
(Икс)
(Элмер Фадд)
(2 3 5 7 11)
(2 3 х у "зоопарк" 2.9)
()
Представление списков в виде прямоугольников и стрелок:
_______________ ________________
| | | | | |
| о | ----|----->| о | о |
|___|___|_______| |____|___|___|___|
| | |
| | |
Элмер Фадд (англ.)
Списки схем могут содержать элементы разных типов:
(1 1,5 х (а) ((7)))
Вот несколько важных функций, которые работают со списками:
length — длина списка
равны? — проверить, равны ли два списка (рекурсивно)
автомобиль — первый элемент списка
cdr — остаток списка
минусы — создать новую ячейку списка (также известную как ячейка cons )
список — составить список
(Для вашего удобства Схема также предопределяет составы автомобиль и cdr , например, (кадры s) есть определить d как (car (cdr s)) . )
Предикаты для списков:
ноль? — список пуст?
пара? — это непустой список?
Вычисление выражений
Пользователи обычно взаимодействуют со схемой через read-eval-print.
цикл ( REPL ). Схема ожидает, пока пользователь введет
выражение, читает его, оценивает и печатает возвращаемое значение.
Выражения схемы (часто называемые S-выражениями , для Символические выражения ) являются либо списками, либо атомами. Списки
состоит из других S-выражений (обратите внимание на рекурсивное определение).
Списки часто используются для представления вызовов функций, где список
состоит из имени функции, за которым следуют ее аргументы. Однако списки
также может использоваться для представления произвольных коллекций данных.
В этих заметках мы обычно пишем:
=> <возвращаемое значение>
когда мы хотим показать S-выражение и оценку этого
S-выражение. Например:
(+ 2 3) => 5
(против 1 () ) => (1)
Правила оценки:
Числа, строки, #f и #t являются литералами, т. е.
оценить для себя.
Символы рассматриваются как переменные, и для их оценки
их привязки просматриваются в текущей среде.
Для списков первый элемент определяет функцию. Остальные
элементы списка определяют аргументы. Оцените первый элемент
в текущих условиях для
найти функцию и
оценить каждую из
аргументы в текущей среде и вызовите функцию для этих значений.
Например:
Использование символов (атомов) и списков в качестве данных
Если мы попытаемся оценить
(перечислите Элмера Фадда) мы получим ошибку. Почему? Потому что
Схема будет рассматривать атом elmer как имя переменной и пытаться искать
за его привязку, которую он не найдет. Поэтому нам нужно «цитировать»
имена Элмер и Фадд, что означает, что мы
хочу схему относиться к ним буквально. Схема предоставляет синтаксис для этого.
Оценка объектов в кавычках заключается в том, что объект в кавычках оценивает сам себя.
Обратите внимание, что есть 3 способа составить список:
‘(xyz) => (xyz)
(cons ‘x (cons ‘y (cons ‘z () ))) => (x y z)
(список ‘x ‘y ‘z) => (x y z)
Внутри заключенные в кавычки символы и списки представляются с помощью специального
функциональная цитата. Когда читатель читает «(a b) это
переводит это в (цитата (a b)), который затем передается на
оценщик. Когда оценщик видит выражение вида (цитата
s-expr) он просто возвращает s-expr. цитата иногда
называется «особой формой», потому что, в отличие от большинства других операций Схемы, она
не оценивает свой аргумент. Кавычка является примером того, что
называется «синтаксическим сахаром».
'х => х
(кавычки х) => х
(Алан Перлис: «Синтаксический сахар вызывает рак точки с запятой».)
Переменные
Схема имеет как локальные, так и глобальные переменные. В схеме переменная
имя, которое привязано к некоторому объекту данных (с помощью указателя). Там
нет объявлений типов для переменных. Правило оценки
символы: символ оценивается как значение переменной, которую он называет. Мы
можно связывать переменные с помощью специальной формы определить:
(определить выражение символа)
Использование определяет связывает символ (ваша переменная
name) к результату вычисления выражения . определить — это особая форма, потому что первый параметр, символ , не оценивается.
Строка ниже объявляет переменную с именем clam (если она не
существует) и делает его ссылкой на 17:
(определение моллюска 17)
моллюск => 17
(определение моллюска 23) ; это привязывает моллюска к 23
(+ моллюск 1) => 24
(определить bert '(a b c))
(определить Эрни Берта)
Схема использует указатели: теперь bert и ernie указывают на один и тот же список.
В 341 мы будем использовать define только для привязки глобальных переменных, и мы
не будет перепривязывать их после привязки, за исключением случаев отладки.
Переменные с лексической областью видимости с let и let*
Мы используем специальную форму let для объявления и привязки локальных,
временные переменные. Пример:
;; общая форма let
(пусть ((имя1 значение1)
(имя2 значение2)
...
(имяN значениеN))
выражение1
выражение2
...
выражениеQ)
;; перевернуть список и удвоить его
;; менее эффективная версия:
(определить (r2 x)
(добавить (обратный х) (обратный х)))
;; более эффективная версия:
(определить (r2 x)
(пусть ((r (обратный x)))
(дописать р р)))
Единственная проблема с Let заключается в том, что пока создаются привязки,
выражения не могут ссылаться на привязки, которые были сделаны ранее.
Например, это не работает, так как x неизвестен вне тела:
(пусть ((х 3)
(у (+ х 1)))
(+ х у))
Чтобы обойти эту проблему, Scheme предоставляет нам let*:
(пусть* ((х 3)
(у (+ х 1)))
(+ х у))
Определение собственных функций
Lambdas: анонимные функции
Вы можете использовать специальную форму lambda для создания
анонимные функции. Эта специальная форма занимает
(лямбда (param1 param2 ... paramk) ; список формальных
выражение) ; тело
лямбда-выражение оценивается как анонимная функция
который при применении (выполнении) принимает k аргументов и возвращает
результат вычисления expr . Как и следовало ожидать,
параметры имеют лексическую область видимости и могут использоваться только в экспр .
Пример:
(лямбда (x1 x2)
(* (- х1 х2) (- х1 х2)))
Оценка приведенного выше примера приводит только к анонимной функции,
но мы пока ничего с ним не делаем. Результат
Выражение lambda может быть применено непосредственно путем предоставления
аргументы, как в этом примере, который оценивается как 49:
((лямбда (x1 x2)
(* (- х1 х2) (- х1 х2)))
2-5) ;
Определение именованных функций
Если у вас возникают проблемы с определением функции, вы часто хотите
сохраните его для последующего использования. Вы достигаете этого, связывая результат
лямбда в переменную с использованием определить , так же, как
вы бы с любым другим значением. (Это иллюстрирует, как функции
первый класс по схеме. Это использование определяет не
отличается от переменных привязки к другим типам значений.)
Поскольку определение функций является очень распространенной задачей, Scheme предоставляет
специальная сокращенная версия определяет , которая не использует лямбда явно:
(определить (имя функции param1 param2 ... paramk)
выражение)
Вот еще несколько примеров использования для определения в этом
путь:
(определить (двойной х)
(* 2 х))
(двойное 4) => 8
(определить (от Цельсия до Фаренгейта c)
(+ (* 1,8 с) 32,0))
(100,0 градусов Цельсия в градусы Фаренгейта) => 212,0
x в функции double является формальным
параметр. Он имеет область видимости только внутри функции. Рассмотрим три
разные х здесь...
Scheme предоставляет три примитива для проверки равенства и идентичности:
экв? это сравнение указателей. Он возвращает #t тогда и только тогда, когда его аргументы
буквально относятся к одним и тем же объектам в памяти. Символы
уникальны ('fred всегда вычисляет один и тот же объект).
Два одинаковых символа равны. Две переменные
которые относятся к одному и тому же объекту, равны.
экв? это как экв? но делает правильные вещи при сравнении
числа.
экв? возвращает #t тогда и только тогда, когда
аргументы eq или , если его аргументы являются числами, которые имеют
такое же значение. экв? не
преобразовывать целые числа в числа с плавающей запятой при сравнении целых чисел и чисел с плавающей запятой.
равны? возвращает true, если его аргументы имеют одинаковую структуру.
Формально мы можем определить
равный? рекурсивно.
равный? возвращает #t, если его аргументы равны eqv, или если
его аргументы - это списки, соответствующие элементы которых равны
(обратите внимание на рекурсию).
Два объекта, которые являются eq, являются одновременно eqv и
равный. Два объекта
равны,
но не обязательно экв. Два объекта, которые
равны не обязательно eqv или
экв. эквалайзер иногда
называется личностью
сравнение и равенство называется сравнением на равенство.
Примеры:
(определить моллюск '(1 2 3))
(определение моллюска осьминога) ; моллюск и осьминог относятся к одному и тому же списку
(eq? 'моллюск 'моллюск) => #t
(eq? моллюск моллюск) => #t
(eq? моллюск осьминог) => #t
(eq? моллюск '(1 2 3)) => #f ; (или (), в схеме Массачусетского технологического института)
(экв? '(1 2 3) '(1 2 3)) => #f
(экв? 10 10) => #t ; (обычно, но зависит от реализации)
(экв? 10. 0 10.0) => #f ; (обычно, но зависит от реализации)
(экв? 10 10) => #t ; всегда
(экв? 10.0 10.0) => #t ; всегда
(экв? 10.0 10) => #f ; нет преобразования между типами
(равно? моллюск '(1 2 3)) => #t
(равно? '(1 2 3) '(1 2 3)) => #t
Схема дает = для сравнения
два числа и приведут один тип к другому.
Например, (равно? 0 0.0) возвращает #f , но (= 0 0.0) возвращает #t .
Логические операторы
Схема предоставляет нам несколько полезных логических операторов, в том числе
и, или, и нет. Операторы и
и или являются специальными формами и не обязательно оценить все аргументы. Они просто оценивают столько аргументов, сколько необходимо
принять решение о возвращении #t или #f (аналогично
&& и || операторы в С++). Однако можно было
легко написать версию, которая оценивает все его аргументы.
(и expr1 expr2 ... expr-n)
; вернуть true, если все выражения верны
; . .. или, точнее, вернуть expr-n, если все expr оцениваются как
; что-то кроме #f. В противном случае вернуть #f
(и (равно? 2 3) (равно? 2 2) #t) => #f
(или expr1 expr2 ... expr-n)
; вернуть true, если хотя бы одно из expr истинно
; ... или, точнее, вернуть выражение-j, если выражение-j является первым выражением, которое
; оценивается чем-то другим, кроме #f. В противном случае вернуть #f.
(или (равно? 2 3) (равно? 2 2) #t) => #t
(или (равно? 2 3) 'fred (равно? 3 (/ 1 0))) => 'fred
(определить (однозначное число x)
(и (> x 0) ( #t
Булевы особенности
В схеме R4 пустой список эквивалентен #f, а все остальное
эквивалентно #t. Однако в R5 пустое
список также эквивалентен #t! Мораль: используйте только #f и #t для логических значений.
константы.
Условные обозначения
, если специальная форма
(если условие true_expression false_expression)
Если условие оценивается как истинное, то результат
при оценке возвращается true_expression ; иначе
результат оценки возвращается false_expression . if это особая форма, например кавычка , потому что она не автоматически оценивает все свои аргументы.
(если (= 5 (+ 2 3)) 10 20) => 10
(если (= 0 1) (/ 1 0) (+ 2 3)) => 5
; обратите внимание, что (/ 1 0) не оценивается
(определить (мой-макс х у)
(если (> х у) х у))
(мой-макс 10 20) => 20
(определить (my-max3 x y z)
(если (и (> x y) (> x z))
Икс
(если (> у z)
у
з)))
Как только мы находим тест, который оценивается как истинный, мы оцениваем
соответствующее выражение и вернуть его значение. Остальные тесты не
оценивается, а все остальные выражения не оцениваются.
Если ни один из тестов не дает истинного результата, мы оцениваем exprn ("еще"
часть) и вернуть его значение. (Вы можете опустить часть else, но это не
хороший стиль.
y).
Таблица истинности определяет результат выполнения операции для всех возможных логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2N строк, так как существует 2N различных комбинаций возможных значений аргументов.
(T)
Когда мы
изучение математических формул типа «$x$ делит $y$» на переменные
предполагается, что они принимают значения в любом дискурсивном универсуме
подходит для конкретного предмета. Вселенная дискурса
обычно ясно из обсуждения, но иногда нам нужно будет
идентифицируйте его явно для ясности.
Вселенная дискурса обычно обозначается $U$.
Чтобы $P\land Q$ были истинными как $P$, так и $Q$
должно быть истинным, иначе оно ложно, например,
Не очевидно (по крайней мере, для большинства людей), под чем
обстоятельства $P\имеет Q$ должно быть правдой. Отчасти это потому, что
«if… then» используется в обычном английском языке более чем одним способом, однако
нам нужно исправить правило, которое позволит нам точно знать, когда $P\ подразумевает
Q$ верно. Конечно, если $P$ истинно, а $Q$ ложно, $P$ не может
подразумевают $Q$, поэтому $P\implis Q$ в этом случае ложно. Чтобы помочь нам с
в других случаях рассмотрим следующее утверждение:
Мы
будет применять операции в этом порядке, начиная с
от первого к последнему: $\lnot$, $\land$, $\lor$, $\implies$
и $\Leftrightarrow$. Так
$$A\подразумевает B\или C\land\lnot D
$$
сокращение от
$$A\подразумевает (B\или (C\land (\lnot D))).
$$
Как и в алгебре, часто разумно включать
несколько дополнительных скобок, чтобы убедиться, что предполагаемый смысл понятен.
Большая часть информации, которую мы обсудили, может быть резюмирована в таблицы истинности . Например, таблица истинности для
$\lnot P$:
Таблица истинности для $(P\land Q)\lor \lnot R$ такова:
посчитай и прочитай.
Это говорит о том, что существует
форма алгебры для логических выражений, аналогичная алгебре
для числовых выражений. Этот предмет называется Булева алгебра и имеет множество применений.
особенно в информатике.
Они называются «двойственными» понятиями — для любого свойства
один, есть почти идентичное свойство, которому удовлетворяет другой,
экземпляры двух операций поменялись местами. Это часто
означает, что когда мы доказываем результат, включающий одно понятие, мы получаем
соответствующий результат для своего двойственного без дополнительной работы.
Важность этого уровня абстракции для
будущее математики трудно переоценить. Вероятно, на
Благодаря этой работе он перешел на должность в Куинс-колледж в Корке.
Заменив $xy$ на $x$, получим $xz=x$, или
$x\подразумевает z$. Этот простой пример логического рассуждения используется более
и далее по математике.
92+bD+c=0$, обработка
$D$ как номер , предоставляет информацию о решениях для
дифференциальное уравнение.
1.4 
компиляторы, редакторы структур, отладчики и т.д.)
См. также «Булево
Особенности» ниже.
В Scheme списки не ограничены, возможно, неоднородны.
коллекции данных. Примеры:
)
е.
оценить для себя.
Кавычка является примером того, что
называется «синтаксическим сахаром».
Эта специальная форма занимает
Вы достигаете этого, связывая результат
Он имеет область видимости только внутри функции. Рассмотрим три
разные 
0 10.0) => #f ; (обычно, но зависит от реализации)
(экв? 10 10) => #t ; всегда
(экв? 10.0 10.0) => #t ; всегда
(экв? 10.0 10) => #f ; нет преобразования между типами
(равно? моллюск '(1 2 3)) => #t
(равно? '(1 2 3) '(1 2 3)) => #t
.. или, точнее, вернуть expr-n, если все expr оцениваются как
; что-то кроме #f. В противном случае вернуть #f
(и (равно? 2 3) (равно? 2 2) #t) => #f
(или expr1 expr2 ... expr-n)
; вернуть true, если хотя бы одно из expr истинно
; ... или, точнее, вернуть выражение-j, если выражение-j является первым выражением, которое
; оценивается чем-то другим, кроме #f. В противном случае вернуть #f.
(или (равно? 2 3) (равно? 2 2) #t) => #t
(или (равно? 2 3) 'fred (равно? 3 (/ 1 0))) => 'fred
(определить (однозначное число x)
(и (> x 0) ( #t
if это особая форма, например 
Leave A Comment