Булева алгебра и логические схемы компьютера. Логические машины.

 

Алгебра логики – это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.

Создателем алгебры логики является английский математик Джордж Буль (19 век), в честь которого она названа булевой алгеброй высказываний

Логические схемы

Во всех современных компьютерах применяется логическая система, изобретенная Джорджем Булем. Тысячи микроскопических электронных переключателей в кристалле интегральной схемы сгруппированы в системы «вентилей», выполняющих логические операции, т.е. операции с предсказуемыми результатами. На приведенных здесь рисунках показаны элементарные логические вентили И, ИЛИ и НЕ. Все остальные логические схемы компьютера могут быть построены на основе вентилей этих трех типов.

Соединенные в различные комбинации, логические вентили дают возможность компьютеру решать задачи с помощью закодированных импульсов его двоичного языка. На вход каждого логического вентиля поступают электрические сигналы высокого и низкого уровней напряжения, которые он интерпретирует в зависимости от своей функции и выдает один выходной сигнал также либо низкого, либо высокого уровня. Эти уровни соответствуют одному из состояний двоичной системы: да - нет, единица - ноль, истина - ложь. Простой вентиль И, например, выдает на выходе 1 в том и только том случае, когда на все его входы поступает 1, что соответствует логическому значению «истина». Действуя в соответствии с определенными правилами, логические вентили координируют движение данных и выполнение инструкций в компьютере. Так, определенный элемент данных может пройти от одного блока к другому только в том случае, если на входах конкретного вентиля И оба сигнала будут равны 1.

Изображенные здесь вентили выполняют логическую операцию И. Они показаны символическими обозначениями, принятыми в электронике. Хотя у каждого вентиля И здесь изображено по два входа, на самом деле число входов может быть и большим. Однако, как у всех логических вентилей, выход у него только один. Вентиль И по определению выдает значение 1, т. е. логическое значение «истина», в том и только том случае, когда на оба его входа поступает 1, т. е. «истина». Три верхних вентиля дают на выходе 0, или «ложь», поскольку ни у одного из них на оба входа не поступает по 1. Лишь у нижнего вентиля на выходе появляется 1, т. е. «истина». Как и вентили И, вентили ИЛИ могут иметь больше двух входов, Но только один выход. Однако к входам этих вентилей «предъявляются менее строгие требования». Как здесь показано, на выходе вентиля ИЛИ 1, или «истина», получается и в том случае, когда по крайней мере на один из его входов поступает 1. Только в одном случае вентиль ИЛИ выдает двоичный 0, или логическое значение «ложь», - когда логическое значение «ложь» поступает на все его входы.

Эти треугольники с кружочком на конце - символические изображения вентиля НЕ, или инвертера. В отличие от вентилей И, ИЛИ вентиль НЕ имеет лишь один вход, значение которого он меняет на обратное, превращая 0 в 1, а 1 в 0. Вентили НЕ часто комбинируют с вентилями И и ИЛИ, в результате чего получаются вентили И-НЕ («и - не») и ИЛИ-НЕ («или - не»). Такие комбинированные схемы обрабатывают входные сигналы так же, как вентили И, ИЛИ, а затем инвертируют выходной сигнал.

Ост здесь.

Логическая Машина

- механическое, электромеханическое или электронно-вычислительное устройство, предназначенное для полуавтоматического или автоматического решения широкого круга математических и логических задач, для управления технологическими и производственными процессами, для оптимальных экономических расчетов, для обработки массивов информации, которые мозг человека не в состоянии охватить, для моделирования форм человеческого мышления. Попытки создать механические устройства для осуществления арифметических операций уходят в далекую древность. Первую логическую машину построил Раймунд Луллий (1235-1315). Его машина состояла из семи вращающихся вокруг одного центра кругов. На каждом из них были написаны слова, выражающие различные понятия, напр. "человек", "знание", "количество" и т. п., и логические операции, напр. "равенство", "противоречие" и т. п. Вращая круги, можно было получать разнообразные сочетания понятий. С помощью своей машины Луллий получал из заданных посылок силлогистические выводы. В первой половине XVII в. французский математик Б. Паскаль (1623-1662) сконструировал машину для выполнения арифметических операций. Идея машинизации процессов умозаключения была теоретически развита немецким философом и ученым Г. Лейбницем (1646-1716) в работе "Об искусстве комбинаторики". Первой подлинно Л. м. считается "демонстратор" Ч. Стенхопа (1753-1816), с помощью которого проверялись не только традиционные, но и т. наз. "числовые" силлогизмы. "Демонстратор" решал элементарные задачи традиционной логики. Научные основы для создания современных Л. м. были заложены благодаря развитию математической логики и кибернетики, а техническая возможность их создания была обеспечена прогрессом в области электроники и автоматики. В 1944 г. в США была построена автоматическая вычислительная машина "Марк-1", имевшая электромагнитное реле и перфоленту, на которой записывались числа и указывались операции с ними. В 1945 г. Дж. фон Нейман предложил помещать закодированную программу вычислений в запоминающее устройство машины, что значительно расширило диапазон ее возможностей. С середины 50-х годов начали создаваться информационно-логические машины, способные хранить значительные записи информации, выбирать из них необходимые данные и производить не только математическую обработку информации, но и логические операции. Л. м. последующих поколений способны осуществлять миллиарды операций в секунду, различать простые рисунки, самообучаться, понимать простые фразы на естественном языке и решать самые разнообразные задачи во многих областях науки, техники, управления и т. д. Принципиальная схема Л. м. включает следующие основные компоненты: 1. Входное устройство, преобразующее внешнюю информацию в последовательность электрических импульсов. 2. Выходное устройство, преобразующее электрические сигналы в последовательность воспринимаемых человеком знаков. 3. Запоминающее устройство, хранящее информацию и часто называемое просто "памятью" машины. Различают оперативную память, емкость которой сравнительно невелика, но отличается быстродействием, и долговременную, внешнюю память, с большим объемом, но меньшим быстродействием. 4. Арифметическое устройство, осуществляющее математические и логические действия. 5. Блок управления, обеспечивающий автоматическое выполнение программы, введенной в машину. Все более широкое использование Л. м. позволяет человеку решать все более сложные задачи, освобождает его от рутинных мыслительных операций и делает человеческий труд все более творческим.

 

9. Основы логики: Логика высказываний, логические языки, таблица истинности.

Логика Высказываний, Или Пропозициональная Логика

- раздел логики, формализующий употребление логических связок "и", "или", "не", "если, то" и т. п., служащих для образования сложных высказываний из простых. Высказывание называется простым, если оно не включает в себя другие высказывания, в противном случае оно называется сложным. В Л. в. простые высказывания рассматриваются в отвлечении от их внутренней (субъектно-предикатной) структуры. Та или иная истинностная оценка высказывания именуется его истинностным значением. В логике классической предполагается, что простое высказывание является либо истинным, либо ложным (см.: Двузначности принцип) и что истинностное значение сложного высказывания зависит только от истинностных значений входящих в него простых высказываний и характера их связи. Так, соединение двух высказываний с помощью связки "и" дает сложное высказывание (именуемое конъюнкцией), являющееся истинным, только когда оба составляющие его высказывания истинны. Сложное высказывание, образованное с помощью связки "или" (дизъюнкция), истинно, если и только если хотя бы одно из двух входящих в него высказываний истинно. Сложное высказывание, образованное с помощью "не" (отрицания), истинно, если только исходное высказывание ложно. Сложное высказывание, полученное из двух высказываний с помощью связки "если, то" (импликация), истинно в трех случаях: оба входящие в него высказывания истинны, оба они ложны, первое из этих высказываний (следующее за словом "если") ложно, а второе (следующее за словом "то") истинно; импликация является ложной только когда первое из составляющих ее высказываний истинно, а второе ложно. Возможны и другие способы образования сложных высказываний. Всего в классической двузначной логике четыре способа образования сложного высказывания из одного высказывания и шестнадцать способов образования сложного высказывания из двух высказываний. Язык Л. в. включает бесконечное множество переменных: р, q, r,..., p1, q1, r1,..., представляющих высказывания, и особые символы для логических связок: & - конъюнкция ("и"), v - дизъюнкция ("или"), ~ - отрицание ("не" или "неверно, что"), -> - импликация ("если, то"). Роль знаков препинания обычного языка играют скобки. Понятие формулы в Л. в. определяется так: отдельная переменная является формулой; если A и В - формулы, то (А&В), (AvB), ~A и (A->B) также формулы. Формулам Л. в., образованным из переменных и связок, в естественном языке соответствуют предложения. Напр., если р есть высказывание "Сейчас ночь", q - высказывание "Сейчас темно" и r - высказывание "Сейчас ветрено", то формула (p->(qvr)) представляет высказывание "Если сейчас ночь, то сейчас темно или ветрено", формула ((q&.r)->p) - высказывание "Если сейчас темно и ветрено, то сейчас ночь", формула (~q->~p) - высказывание: "Если неверно, что сейчас темно, то сейчас не ночь" и т. п. Подставляя вместо переменных другие высказывания, получим другие переводы указанных формул на обычный язык. Каждой формуле Л. в. можно поставить в соответствие таблицу истинности, указывающую зависимость истинностного значения формулы от истинностных значений входящих в нее переменных. Напр., формула (~q->~p) принимает значение "ложно" только в случае ложности q и истинности р. Формула Л. в. называется тождественно-истинной, или тавтологией, если и только если она принимает значение "истинно" при всех распределениях истинностных значений входящих в нее простых высказываний. Формула, принимающая при всех распределениях значение "ложно", называется противоречием. Тавтологии выражают логические законы. К тавтологиям относятся, в частности, формулы: (р->р) - закон тождества, ~(р&~р) - закон непротиворечия, (pv~p) - закон исключенного третьего, (p->q)->(~q->~p) - закон контрапозиции. Множество тавтологий бесконечно. Л. в. может быть представлена также в форме логического исчисления, в котором задается способ доказательства некоторых высказываний (формул), называемых теоремами. Исчисление может быть формализовано с помощью аксиоматического метода. При этом указываются формулы, принимаемые в качестве аксиом, и задаются правила вывода, позволяющие получать из аксиом теоремы. Аксиоматическое исчисление высказываний строится таким образом, чтобы класс теорем совпадал с классом тавтологий, т. е. чтобы каждая теорема была тавтологией и каждая тавтология - теоремой (см.: Полнота). По отношению к аксиоматическому построению встают также вопросы о его непротиворечивости и независимости принятых аксиом и правил вывода. Наряду с классической Л. в., предполагающей, что всякое высказывание является истинным или ложным, существуют многообразные неклассические Л. в. В числе последних - многозначные Л. в., интуиционистская Л. в. и др.

Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

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

Законы логики высказываний

1. А <=> A закон двойного отрицания;

2. A&B <=> B&A коммутативность конъюнкции;

3. AVB <=> BVA коммутативность дизъюнкции;

4. A&(B&C) <=> (A&B)&C ассоциативность конъюнкции;

5. AV(BVC) <=> (AVB)VC ассоциативность дизъюнкции;

6. A&(BVC) <=> (A&B)V(A&C) дистрибутивность конъюнкции относительно дизъюнкции;

7. AV(B&C) <=> (AVB)&(AVC) дистрибутивность дизъюнкции относительно конъюнкции;

8. A&A <=> A

9. AVA <=> A

1O. AVA <=> И закон исключенного третьего;

11. A&A <=> Л закон не противоречия;

12. A&И <=> A

13. AVИ <=> И

14. A&Л <=> Л

15. AVЛ <=> A

16. (A&B) <=> A V B законы де Моргана;

17. (AVB) <=> A & B

18. A => B <=> A V B замена импликации.

Язык Логики

— специально создаваемый современной логикой для своих целей язык, способный следовать за логической формой рассуждения и воспроизводить ее даже в ущерб краткости и легкости общения. Я. л. является языком формализованным. Построение его предполагает принятие особой теории логического анализа. Логика традиционная пользовалась для описания правильного мышления обычным языком, дополненным немногими специальными символами. Этот язык имеет, однако, целый ряд черт, мешающих ему точно передавать форму мысли. Он является аморфным как со стороны своего словаря, так и в отношении правил построения выражений и придания им значений. В нем нет четких критериев осмысленности утверждений. Не выявляется строго логическая форма рассуждений. Значения отдельных слов и выражений зависят не только от них самих, но и от их окружения. Многие соглашения относительно употребления слов не формулируются явно, а только предполагаются. Почти все слова имеют не одно, а несколько значений. Одни и те же объекты порой могут называться по-разному или иметь несколько имен. Есть слова, не обозначающие никаких объектов, и т. д. Все это не означает, что обычный язык никуда не годен и его следует заменить какой-то искусственной символикой. Он вполне справляется с многообразными своими функциями. Но, решая многие задачи, он лишается способности точно передавать логическую форму. Для целей логики необходим искусственный язык, строящийся по строго сформулированным правилам. Этот язык не предназначен для общения, он должен служить только одной задаче - выявлению логических связей наших мыслей, но решаться она должна эффективно. В формализованном Я. л. слова обычного языка заменяются различными специальными символами. В нем четко разграничены синтаксическая и семантическая части, разделение которых в обычном языке во многом условно. Вначале язык логики строится без всякой ссылки на ту действительность, которую он будет описывать. И только потом вводятся правила придания значений употребляемым в нем комбинациям знаков, указывается его интерпретация. Построение языка отличается тщательностью, с какой формулируются синтаксические и семантические правила, отсутствием неправильностей и исключений. Разделение синтаксиса и семантики позволяет определить понятие вывода логического чисто формально, не обращаясь к содержанию конструируемых и преобразуемых выражений. Вывод оказывается подчиненным простым предписаниям, подобным правилам сложения и вычитания. Исчезают неясность и двусмысленность, всегда присутствующие при обращении с такой трудно уловимой вещью, как «смысл выражения». Место обычного в процессе рассуждения оперирования идеальными смыслами занимает манипулирование материальными вещами — цепочками знаков. Выведение одних идей из других превращается в «вычисление» по простым правилам. Научная революция в логике во второй половине XIX — начале XX в. привела к созданию логически совершенного языка. Последний сделал возможным дальнейшее углубленное изучение и описание закономерностей правильного мышления.

Логическое программирование в первую очередь ассоциируется с языком Prolog. Prolog гораздо менее распространенный и известный язык, чем COBOL, Fortran или С.

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

Таблица истинности – это таблица, устанавливающая соответствие между всеми возможными наборами логических переменных, входящих в логическую функцию, и значениями функции. Таблица, с помощью которой уста­навливается истинностное значение сложного высказывания при данных значениях входящих в него простых высказываний. В клас­сической математической логике предполагается, что каждое про­стое (не содержащее логических связок) высказывание является либо истинным, либо ложным, но не тем и другим одновременно. Нам не известно, истинно или ложно данное простое высказыва­ние, чтобы установить это, потребовалось бы обратиться к фактам действительности, но логика этого не делает.

 

Графы и деревья.

Термин граф впервые появился в работах венгерского математика Д.Кенинга в 1936 году, хотя ряд задач по теории графов решался еще Л.Эйлером в XVIII веке.

Граф - это двойка <V, E>, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно2). Две вершины, связанные между собой ребром, равноправны, и именно поэтому такие графы называются неориентированными: нет никакой разницы между "началом" и "концом" ребра.

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

Деревья являются в некотором смысле простейшим видом графов.Связаный ациклический граф называется деревом.

Одним из частных случаев графа является дерево.

 

Определим формально дерево как конечное множество Т, состоящее из одного или более узлов, таких, что:

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

остальные узлы (исключая корень) содержаться в m (большее или равное 0) попарно не пересекающихся множествах Т1, …, Тm, каждое из которых в свою очередь является деревом. Деревья Т1, …, Тm называются поддеревьями данного корня.

Ориентированные графы - это граф, все ребра которого имеют направление. Такие направления ребра называются дугами, в отличие от ребер дуги соединяют две неравноправные вершины, одна из них называется началом дуги, а вторая – концом дуги.

Любое ребро – это пара дуг, которые направлены навстречу друг другу.

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

орграф (смешанный, т.к. есть ребра)

4-5 – это ребро, т.к. нет стрелки.

 

 

2.Неориентированные графы.

Неориентированный граф с шестью вершинами и семью рёбрами

В математической теории графов и информатике граф — это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или ребрах. Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Например, строение Википедии можно смоделировать при помощи ориентированного графа (орграф), в котором вершины — это статьи, а дуги (ориентированные рёбра) — это связи, созданные гиперссылками

 

2.Примеры деревьев.