Математические и логические основы информатики - Программирование, компьютеры и кибернетика методичка

Главная

Программирование, компьютеры и кибернетика
Математические и логические основы информатики

Логическая равносильность преобразования, его применение к математическим доказательствам. Применение аппарата булевских функций к синтезу комбинационных схем. Вычисление логических операций выполняемых микропроцессором. Значение истинности высказываний.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Под высказыванием мы будем понимать повествовательное предложение, относительно которого объективно можно сказать, что оно либо исти н но , либо ложно.
Высказывания, подобные приведенным выше, называют простыми высказываниями. Они не могут быть «разложены» на более элементарные высказывания, относительно которых сохранилась бы объективная возможность оценить их истинность.
Из одних высказываний могут составляться (строиться) другие, более сложные высказывания. Такие высказывания мы будем называть составными , или сложными высказываниями.
В русском языке (и не только в русском) составные высказывания строятся из простых с помощью союзов (и, или), частицы (не) и словосочетаний (если…,то...;…тогда и только тогда, когда…; …если, и только если…;…необходимо и достаточно для… и т.д.)
Законы Де Моргана : (A&B) AB, (AB) AB.
(tertium non datur - третьего не дано): AA И.
Закон снятия двойного отрицания : A A.
Законы поглощения A&(AB)A, A(A&B)A.
Используя теперь приведенные свойства и законы, можно осуществлять эквивалентные (тождественные) преобразования формул логики высказываний, подобно тому, как мы преобразовывали формулы теории множеств. Но прежде уточним некоторые понятия и определения.
Дадим индуктивное определение формулы логики высказыв а ний :
Всякая пропозициональная константа и переменная есть формула логики высказываний.
Если F, Ф - формулы логики высказываний, то следующие последовательности символов также будут формулами логики высказываний:
Те и только те последовательности символов будут формулами логики высказываний, для которых это следует из пп.1 и 2 данного определения. ) F и Ф называют в этом случае подформулами формулы логики высказываний.)
Истинностным значением (или просто значением ) формулы логики высказ ы ваний является значение истинности, получаемое при вычислении результатов всех логических операций, с помощью которых строится формула, при той или иной ко м бинации значений пропозициональных переменных и констант, входящих в фо р мулу.
При вычислении значения формулы мы будем руководствоваться (как и в школьной а лгебре) круглыми скобками (,) и следующим приоритетом (старшинством) операций:
дизъюнкция (), строгая дизъюнкция (),
Операции перечислены в порядке убывания приоритета: отрицание () имеет самый высокий приоритет, а эквиваленция () - самый низкий. Старшинство операций учитывается, если скобки не определяют однозначно порядок вычисления.
Покажем на примерах как вычисляется значение истинности формул логики высказываний при заданных значениях истинности входящих в формулу пропозициональных переменных и констант. Для этого воспользуемся универсальным для логики высказываний методом - методом истиннос т ных таблиц .
Прежде всего, заметим, что порядок вычисления значения истинности этой формулы определяется частично скобками, а частично старшинством операций. Этот порядок и вычисления в соответствии с ним представлены в таблице:
Результирующее значение И представлено в последней строке в столбце, соответствующем последней выполняемой операции отрицания (в выделенной жирной линией клетке).
Предпоследнюю и последнюю строки в будущем будем объединять в одну, чтобы сократить размеры таблицы.
Тождественно-истинные и тождественно-ложные формулы логики высказываний. Логическая равносильность формул. Равносильные преобразования формул
Формулу логики высказываний, принимающую значение истинности И (ист ина) на любом наборе значений для пропозициональных переменных, входящих в формулу, называют тождественно-истинной формулой , или тавт о логией .
Формулу логики высказываний, принимающую значение истинности Л (ложь) на любом наборе значений для пропозициональных переменных, входящих в формулу, называют тождественно-ложной формулой , или противор е чием .
Формулу логики высказываний, не являющуюся ни тождественно-истинной, ни тождественно ложной, называют выполн и мой.
Пусть формулы F и Ф логики высказываний содержит пропозициональные переменные X1, X2, … , Xn. Будем считать эти формулы логически равносильными , если они принимают одинаковые значения истинности на соответствующих наборах значений для пропозициональных переменных X1,X2,…,Xn, входящих в эти формулы.
Если множества пропозициональных переменных, входящих в формулы F и Ф не совпадают, то можно добиться этого совпадения, введя в ту или другую формулу недостающую переменную в качестве "фиктивной". Пусть, например, формула F не содержит пропозициональной переменной Xi. Тогда эту переменную можно ввести в формулу F "фиктивно", заменив формулу F на формулу F( Xi Xi) или на формулу F&( Xi Xi), которые на основании закона противоречия, закона исключенного третьего и свойств логических констант Л и И, равносильны F. Аналогично можно "фиктивно" ввести в формулы F и Ф все другие недостающие переменные. Это соображение легко распространить на любое число формул.
Как мы условились выше, тот факт, что формулы F и Ф логически равносильны будем обозначать FФ.
Отношение равносильности формул, очевидно, обладает свойством транзитивности: если FФ и Ф, то F.
Приведенные выше свойства операций и законы логики высказываний, как легко проверить с помощью таблиц истинности, выражают логическую равносильность (эквивалентность) тех или иных формул.
Кроме приведенных выше равносильностей в логике высказываний большое значение имеют и другие, среди которых отметим следующие:
Логические равносильности играет важную роль в логике высказываний. Они фактически являются правилами и законами логических рассуждений, законами правильного мышления. ) Естественно, логикой высказываний не исчерпывается все многообразие логических рассуждений. Кроме логики высказываний, важное значение имеют логика предикатов, модальная логика, нормативная логика, временная логика, многозначная логика, нечеткая логика и т.д.) Ниже мы покажем их применение, например, к анализу структуры математических доказательств.
На основании перечисленных выше равносильностей, к которым относятся свойства логических операций, логические законы и т.д., осуществляются равносильные (тождественные) преобразования формул логики высказываний с целью упрощения выражений или приведения к определенному виду (подобно тому, как это делается в школьной алгебре на основании свойств арифметических операций, алгебраических законов и иных тождественных соотношений).
Вывод следствий в логике высказываний
Пусть дана совокупность формул логики высказываний F={F1,F2,F3,…,Fm}. Формулы множества F называют посылками (или гипотезами ). Определим понятие логического вывода формулы Ф из множества посылок (гипотез) F.
Вначале определим содержательно понятие логического следствия.
Будем говорить, что формула Ф является логическим следствием множества формул F1,F2,F3,…,Fn, если формула F1&F2&F3&…&FnФ является тождественно-истинной (или тавтологией).
Например, формула X является логическим следствием формул (XY) и (XY), поскольку формула (XY)&(XY)X тождественно истинна, в чем легко убедиться с помощью таблицы истинности:
Ясно, что если две формулы равносильны, то каждая из них является логическим следствием другой.
Построение логического вывода некоторой формулы основывается на применении в процессе вывода специальных правил, называемых прав и лами вывода
Наиболее часто используются следующие правила вывода:
Правило замены формулы равносильной. В процессе вывода в любой момент любую формулу (или подформулу) можно заменить равносильной ей формулой.
Например, формулу (AB) в любой момент можно заменить равносильной ей формулой A&B (второй закон Де Моргана), а формулу AA - пропозициональной константой И (закон исключенного третьего).
Правило подстановки . Если в формулу F вместо всех вхождений пропозициональной переменной Xi подставить одну и ту же формулу , то полученная в результате формула будет логическим следствием формулы F.
Правило modus ponens . Это правило позволяет из двух формул X и XY выводить третью формулу Y.
Правило modus tollens . Это правило формулируется так: из формул X&Y и Y выводится формула X.
Формула X является логическим следствием формул X&Y и Y в смысле приведенного выше определения, поскольку формула ((X&Y)&Y)X является тождественно-истинной (тавтологией), в чем можно убедиться с помощью следующей таблицы истинности:
Например, из формул (AB)&C и C по правилу modus tollens выводится формула (AB).
Итак, можно следующим образом более формально определить понятие логического вывода (и логического следования):
Логическим выводом (или просто, выводом ) формулы Ф из множества посылок (гипотез) F={F1, F2, F3, … , Fm} называют последовательность формул вида: Ф1,Ф2,…,Фi-1,Фi,…,Фn=Ф, таких, что либо Фi - тавтология, либо Фi F, либо Фi является конъюнкцией формул из F, либо Фi получена из формул множества F, или тавтологий логики высказываний, или ранее выведенных в данном выводе формул Ф1, Ф2, …,Фi-1 с помощью правил вывода.
Формулу Ф будем называть в этом случае логическим следств и ем множества формул F={F1,F2,F3,…, Fm}.
Тот факт, что формула Ф выводима из множества посылок F={F1,F2,F3,…, Fm} будем обозначать: F1,F2,F3,…, Fm Ф.
Заметим, что в соответствии с определением вывода все тавтологии логики высказываний считаются выводимыми формулами, притом из пустого множества посылок, то есть, если A - тавтология, то A.
Примем без доказательства следующую теорему, которая называется теоремой дедукции.
Если F1,F2,F3,…, Fm Ф, то F1,F2,F3,…, Fm-1 (Fm Ф), и наоборот.
Эта теорема говорит о возможности переноса формул логики высказываний через знак выводимости .
Замечание: m-кратное применение теоремы дедукции приведет к утверждению выводимости формулы
Применение логики высказываний к анализу математических
Рис.2.2. Вид переключательной схемы.
Каждому переключателю схемы сопоставим пропозициональную переменную Xi, которая будет принимать значение И (истина) или Л (ложь), если соответствующий переключатель замкнут или разомкнут (то есть, не проводит электрический ток).
Поскольку функция участка электрической цепи состоит в том, чтобы проводить электрический ток, то два участка, содержащие одни и те же переключатели и проводящие или не проводящие ток при одном и том же состоянии всех выключателей , мы будем считать "равными" и не различать между собой.
Легко сообразить, что участку цепи, представляющему собой последовательное соединение двух переключателей X1 и X2 будет отвечать формула логики высказываний, представляющая собой конъюнкцию пропозициональных переменных X1 и X2, то есть, X1&X2 (что означает, что такой участок проводит ток тогда и тогда, когда оба переключателя X1 и X2 замкнуты), а участку цепи, представляющему собой параллельное соединение двух переключателей X1 и X2 - формула, представляющая собой дизъюнкцию пропозициональных переменных X1 и X2, то есть, X1X2. Сказанное представлено на рис. 2.3.
Рис. 2.3. Соответствие формул логики высказываний видам соединения переключателей.
Условимся обозначать через И всегда замкнутый контакт, а через Л - всегда разомкнутый. На схемах это будет выглядеть так, как представлено на рис. 2.4.
Рис.2.4. Соответствие логических констант всегда замкнутому и всегда разомкнутому контактам.
Условимся, наконец, обозначать через Xi и Xi такую пару контактов, что когда контакт Xi замкнут, контакт Xi обязательно разомкнут, и наоборот. Техническое осуществление такой пары контактов показано на рис.2.5.
Рис.2.5. Реализация контактов Xi и Xi.
Ясно, что параллельное и последовательное соединение переключательных схем обладает свойствами коммутативности, ассоциативности, идемпотентности.
Несколько сложнее проверяется выполнимость двух законов дистрибутивности:
Приведены попарно эквивалентные переключательные схемы, подтверждающие справедливость указанных законов дистрибутивности для переключательных схем.
Таким образом, все законы логики высказываний имеют аналоги в логике переключательных схем. Это, во-первых, позволяет моделировать сложные высказывания с помощью электрических цепей. Во-вторых, конструировать (синтезировать) переключательные схемы, удовлетворяющие наперед заданным условиям (которые могут быть и достаточно сложными).
Многим из читателей, мы полагаем, приходилось иметь дело с так называемыми числовыми функциями: алгебраическими, тригонометрическими, логарифмическими и т.д. Все они характеризовались тем, что область определения и область значений функций представляли собой подмножества множества действительных чисел.
Например, функция y = f(x), задаваемая формулой y = sin(x) + 1, имеет в качестве области определения (обычно обозначается буквой Х) все множество действительных чисел, а в качестве области значений (чаще обозначаемой буквой Y) множество неотрицательных чисел, принадлежащих интервалу [0, 2]; функция y = (x) , задаваемая формулой (x)=|lgx|+5, в качестве области определения имеет множество всех положительных действительных чисел, а в качестве области значений - множество положительных действительных чисел, больших 5.
Рассматриваемые нами здесь булевские ( логические ) функции характеризуются тем, что аргументы и сама функция принимают значения из множества логических констант {И, Л}.
В теории булевских функций чаще используются "числовые" эквиваленты логических констант: 1 вместо И, 0 - вместо Л. Ниже мы будем придерживаться именно этих обозначений.
Булевская функция в общем случае может содержать n аргументов: y=f(x1,x2,…,xn).
Как и математические функции, булевские функции могут задаваться: словесно, таблично или аналитически. Мы будем использовать последние два способа задания булевских функций: табличный (в виде таблиц истинности) и аналитический (в виде формул логики высказываний). Одна и та же функция может, естественно, задаваться по-разному.
Булевских функций от одной переменной всего 4. Эти функции и задающие их формулы логики высказываний приведены в следующей таблице:
Формулы логики высказываний, задающие функции
ц2(x) = x (совпадает с переменной х)
ц3(x) = x (является отрицанием переменной х)
Булевских функций от двух переменных всего насчитывается 16. Все они представлены в следующей таблице:
Формулы логики высказываний, задающие функции
f3(x,y) = (xy) (отрицание импликации)
f4(x,y) = x (совпадает с переменной x)
f5(x,y) = (yx) (отрицание обратной импликации)
f6(x,y) = y (совпадает с переменной y)
f9(x,y) = xy (конъюнкция отрицаний)
f12(x,y) = yx (обратная импликация)
f15(x,y) = (xy) (отрицание конъюнкции)
Естественно, многие из перечисленных функций могут быть заданы другими, но равносильными формулами логики высказываний.
Областью определения такой булевской функции будет n-тая декартова степень множества {0,1}, то есть всевозможные двоичные наборы длины n вида <12…n>, где i{0,1}. Число таких всевозможных наборов (n-ок) составляет 2n.
Область значений булевской функции от n переменных - это множество {0,1}.
В дальнейшем мы будем рассматривать только всюду определенные булевские функции, то есть область определения таких функций совпадает с n-той декартовой степенью множества {0,1}.
Булевские функции от большего числа переменных могут быть так же заданы таблично, или с помощью формул логики высказываний , или в виде суперпозиции ( взаимной по д становки ) булевских функций одной и/или двух переменных.
Например, булевская функция y=f(x,y,z), задаваемая формулой логики высказываний x&y x&y z может быть задана в виде следующей суперпозиции функций от одной и двух переменных: y=f8(f8(f2(x,y),f9(x,y)),ц2(z)).
Учитывая принципиальную возможность выразить булевскую функцию от любого числа переменных в виде суперпозиции (взаимной подстановки) булевских функций от одной и двух переменных, мы чаще будем использовать либо табличный способ задания таких функций, либо с помощью формул логики высказываний.
Табличный способ задания булевских функций от одной и двух переменных (см. приведенные выше таблицы, определяющие эти функции) наводит нас на некоторые соображения:
число наборов истинностных значений, на которых определена булевская функция от n переменных, составляет 2n (при n=1 это число составляет 2, при n=2 - 4);
значение каждой булевской функции от n переменных представляет собой двоичный набор длины 2n;
каждая булевская функция отличается от любой другой булевской функции с тем же числом переменных своим значением хотя бы на одном из таких наборов
А отсюда можно сделать предположение о том, число N различных булевских функций от n переменных равно числу различных двоичных наборов длины 2n, то есть:
При n=1 это число равно 4, при n=2 - 16, n=3 - 256, n=4 - 65536 и т.д.
В предыдущем пункте было отмечено, что можно выразить любую булевскую функцию от n переменных в виде суперпозиции (взаимной подстановки) булевских функций от одной и двух переменных. В свою очередь эти функции задаются формулами, содержащими логические операции: отрицание(), конъюнкцию (&),строгую дизъюнкцию (), дизъюнкцию(), импликацию(), эквиваленцию ().
Но как известно из логики высказываний, операции логики высказываний строгая дизъюнкция (), импликация (), эквиваленция () могут быть выражены через дизъюнкцию (), конъюнкцию (&) и отрицание ().
В свою очередь, дизъюнкция () может быть выражена через конъюнкцию (&) и отрицание (), а конъюнкция (&) - через дизъюнкцию () и отрицание ().
Таким образом, конъюнкция и отрицание, а также дизъюнкция и отрицание, образуют полную систему логических связок , то есть через эти операции могут быть выражены все остальные.
Более того, можно определить логическую операцию, через которую выражаются все шесть операций: отрицание (), конъюнкция (&), дизъюнкция (), строгая дизъюнкция (), импликация (), эквиваленция (). Таковой, например, является операция, соответствующая сложному союзу "не А или не В" ("или" соединительное). Эта операция обозначается символом (например, АВ) и получила название штрих Шеффера . Штрих Шеффера определяется с помощью следующей таблицы:
Как легко видеть, штрих Шеффера представляет собой отрицание конъюнкции: XY XY (X&Y).
Таким образом, через штрих Шеффера могут быть выражены конъюнкция и отрицание, а значит и все остальные операции логики высказываний. То есть система логических связок, содержащая единственную операцию - штрих Шеффера, является полной.
Есть еще одна логическая операция, аналогичная штриху Шеффера и называемая стрелкой Пирса . Она обозначается символом и представляет собой отрицание дизъюнкции (или конъюнкцию отрицаний): XY (XY) X&Y.
Таким образом, через стрелку Пирса могут быть выражены дизъюнкция и отрицание, а значит и все остальные операции логики высказываний. То есть система логических связок, содержащая единственную операцию - стрелку Пирса, является полной.
Систему булевских функций будем называть функционально полной , если любую булевскую функцию можно выразить в виде суперпозиции (взаимной подстановки) функций из этой системы.
В соответствии с высказанными выше соображениями о полноте системы логических связок и задании булевских функций формулами логики высказываний, можно сделать вывод о функциональной полноте следующих систем булевских функций:
S0 = {ц3(x), f2(x,y), f8(x,y)} - отрицание, конъюнкция, дизъюнкция.
S1 = {ц3(x), f2(x,y)} - отрицание, конъюнкция.
S2 = {ц3(x), f8(x,y)} - отрицание, дизъюнкция.
S3 = {f15(x,y)} - отрицание конъюнкции (штрих Шеффера).
S4 = {f9(x,y)} - отрицание дизъюнкции (стрелка Пирса).
S5 = {ц3(x), f14(x,y)} - отрицание, импликация.
В последующем мы увидим, что с точки зрения проектирования вычислительных устройств особый интерес представляют S3 и S4.
Общий критерий функциональной полноты системы булевских функций, выражающий необходимые и достаточные условия, носит название критерия Поста-Яблонского. ) См. книгу: Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. -М.:Наука, 1966. -120 с. Его изложение выходит, к сожалению, за рамки настоящего пособия.
Рис.2.23. Функциональная схема одноразрядного двоичного сумматора на два входа.
Рассмотрим теперь одноразрядный двоичный сумматор на три входа. Схематическое представление его на рис.2.24.
В отличие от предыдущего случая теперь мы учитываем перенос из младшего разр яда. Здесь: xi - i- тая цифра числа X; yi - i-тая цифра числа Y; pi - перенос из предыдущего, i-го разряда; zi - i-тая цифра результата сложения - числа Z; pi+1 - перенос в следующий, (i+1)-ый разряд.
Входы сумматора - xi, yi, pi, выходы сумматора - zi и pi+1.
Опишем выходы сумматора как булевские функции его входов в виде следующей таблицы:
Соответствующие схема из функциональных элементов представлены на рис.2.25.
Рис.2.25. Функциональная схема одноразрядного двоичного сумматора на три входа.
Сложение n-разрядных двоичных чисел можно осуществить, соединив n сумматоров таким образом, как это показано на рис.2.26.
В данной схеме сумматора первый элемент имеет два входа, а все остальные элементы - по три. Появление 1 на выходе yn+1 означает переполнение разрядной сетки, то есть попытка представить число, содержащее больше, чем n двоичных разрядов.
Рис.2.26. Схема n-разрядного двоичного сумматора.
В некоторых схемах сумматоров "замыкают" выход pn+1 последнего элемента на вход p1 первого. Тогда все элементы схемы сумматора будут иметь по три входа. Такое сложение называют циклическим. Оно находит свое применение при выполнении арифметических операций в ЭВМ.
Работа n-разрядного двоичного сумматора напоминает замук типа "молния". Но есть существенная разность: замук застегивается "шаг за шагом", последовательно. А сложение на двоичном сумматоре осуществляется "параллельно" за один шаг (такт), и выход полностью определяется текущим состоянием входов, независимо от их количества. То есть, если в момент времени t подать 2n сигналов на входы xn,xn-1, xn-2, … ,x2, x1 и yn,yn-1, yn-2,…,y2 ,y1, то n сигналов на выходах сумматора zn, zn-1, zn-2, … ,z2, z1 появятся в тот же момент времени, без задержки. Схемы из функциональных элементов называют поэтому комбинац и онными схемами , или схемами без памяти . Они не запоминают результатов своей предыдущей работы.
Естественно, вычислительные устройства должны обладать "памятью". Ее наличие даст возможность конструировать счетчики, арифметические регистры и различные "умные" схемы, которые выполнив одну интересную функцию, начинают выполнять другую, не менее интересную.
Такие схемы и способы их анализа и синтеза мы рассмотрим ниже.
Логические операции, выполняемые микропроцессором
Микропроцессор компьютера способен выполнять основные логические операции: конъюнкцию & (обозначение AND), дизъюнкцию (обозначение OR), отрицание (обозначение NOT), строгую дизъюнкцию (или сложение по модулю 2) (обозначение XOR).
Особенностью выполнения логических операций микропроцессором является то, что они выполняются над двоичными кодами (словами, полусловами, двойными словами) пора з рядно .
Со школы читатель привык к слову алгебра. При этом под алгеброй, как правило, понимается раздел математики, посвященный изучению свойств числовых (арифметических) операций (сложение, вычитание, умножение, деление, возведение в степень, извлечение корня и т.д.), выражений, тождеств, уравнений и т.п.
Но, вообще говоря, слово алгебра в математике понимается значительно шире.
А именно: Алгеброй называют множество объектов любой природы с определенными и замкнутыми на этом множестве операциями.
Если какая-либо операция определена на множестве Q и результат ее также принадлежит этому множеству, то говорят, что операция замкнута на этом множестве, или множество замкнуто относительно операции . Например, множество натуральных чисел N замкнуто относительно операций сложения и умножения натуральных чисел, но не замкнуто относительно операций вычитания и деления, которые могут в качестве результата давать значения, не принадлежащие множеству натуральных чисел (вычитание - отрицательные числа, а деление - дробные).
С этой точки зрения, арифметика - это алгебра с операциями сложения и умножения, замкнутыми на множестве натуральных чисел. Если к числу операций добавить вычитание, то, строго говоря, это уже не будет алгебра.
Рассмотренная в § 1 настоящей главы теория множеств также является алгеброй в указанном выше смысле. Это алгебра множеств, объектами которой являются множества, а определенными и замкнутыми на этих объектах являются операции объединения, пересечения, дополнения.
Точно так же, рассмотренная в § 2 настоящей главы логика высказываний является алгеброй. Это алгебра высказываний, объектами которой являются высказывания, а определенными и замкнутыми на этих объектах являются операции дизъюнкции, конъюнкции и отрицания.
Две последние алгебры принадлежат к особому типу алгебр, называемых булевыми. ) Название булевы эти алгебры получили в честь известного английского математика Джорджа Буля (1815-1864).)
Булева алгебра представляет собой множество объектов (любой, но одинаковой, природы) с двумя «особыми» объектами («константами») - «единица» (I) и «нуль» (О), и двумя замкнутыми на множестве объектов операциями «сложения» (+) и «умножения» (), обладающими следующими свойствами:
дистрибутивность + относительно и относительно +:
A+(BC)=(A+B) (A+C), A(B+C)=(AB)+(AC);
Кроме того, «особые» объекты («константы») I и O обладают следующими свойствами:
С точки зрения этого определения алгебра множеств является булевой алгеброй, в которой роль «сложения» играет операция объединения множеств (), роль «умножения» - операция пересечения множеств (), роль константы «нуль» - пустое множество (), роль «единицы» - универсальное множество (U). Легко проверить, что все указанные выше свойства операций и констант булевой алгебры здесь выполняются.
Алгебра высказываний также является булевой алгеброй. В ней роль «сложения» играет операция дизъюнкции (), роль «умножения» - операция конъюнкции (&), роль “нуля” - логическая константа Л, роль “единицы” - логическая константа И. И опять-таки легко проверить, что все указанные выше свойства операций и констант булевой алгебры выполняются.
Аналогично можно убедиться в том, что «алгебра переключательных схем» также является булевой: «сложению» будет соответствовать параллельное соединение контактов, «умножению» - последовательное соединение, константе «нуль» - всегда разомкнутый контакт, «единице» - всегда замкнутый контакт. ) Более подробную информацию о булевых алгебрах можно получить в книге: И.М. Яглом. Необыкновенная алгебра. -М.: Наука, 1968. -70с.)
В заключение приведем пример еще одной булевой алгебры - «алгебры максимумов и минимумов». Примем в качестве объектов (элементов) нашей алгебры, например, множество всех чисел отрезка [0,1], т.е. 0х1. В качестве операции «сложения» будем рассматривать операцию взятия максимального из двух чисел x и y и обозначать ее max (x,y), в качестве операции «умножения» - операцию взятия минимального из двух чисел x и y и обозначать ее min (x,y). В качестве константы «нуль» примем минимальное число из рассматриваемого отрезка, то есть число 0, а в качестве «единицы» - максимальное число из рассматриваемого отрезка - 1.
Легко проверить, что для определенных таким образом констант и операций выполняются все свойства булевой алгебры.
min (x,y)=min(y,x), max (x,y)=max(y,x);
min (x, min (y,z)) =min (min (x, y),z),
max (x, max (y,z)) =max (max (x, y),z);
дистрибутивность min относительно max:
min (x, max(y,z)) = max(min(x,y),min(x,z)),
max (x, min(y,z)) = min(max(x,y),max(x,z));
min(x,0)=0, min(x,1)=x, max(x,0)=x, max(x,1)=1.
Рекомендация : Проверьте (хотя бы на примерах) справедливость этих соотношений
Применение математических методов для решения логических задач и построения логических схем. Определение и реализация булевых функций. Основные схемы функциональных элементов. Программируемые логические матрицы. Правила составления таблицы истинности. курсовая работа [821,6 K], добавлен 19.03.2012
Основные понятия алгебры высказываний. Характеристика главных законов алгебраической логики, сущность логических операций и определение порядка их проведения. Практическое применение в информатике табличного и алгебраического задания булевских функций. курсовая работа [662,0 K], добавлен 23.04.2013
Типовые комбинационные схемы. Основы математического аппарата анализа и синтеза логических устройств. Функциональная полнота элементов Шеффера и Пирса. Логические элементы, образующие логический базис. Особенности синтеза схем с запрещенными комбинациями. методичка [977,1 K], добавлен 28.04.2009
Понятие высказывания, операции над простыми высказываниями, таблицы истинности. Примеры построения таблиц истинности сложных высказываний. Таблица истинности импликации. Закон тождества, противоречия, двойного отрицания. Решение логических задач. курсовая работа [507,3 K], добавлен 23.04.2013
Двоичная система исчисления. Характеристика понятий систем исчисления, значение позиции. Десятичные числа и их двоичные и шестнадцатеричные эквиваленты. Двоичные логические элементы, обработка цифровых сигналов. Построение комбинационных логических схем. учебное пособие [68,7 K], добавлен 09.02.2009
Основные понятия алгебры логики. Логические основы работы ЭВМ. Вычислительные устройства как устройства обработки информации. Основные формы мышления. Обзор базовых логических операций. Теоремы Булевой алгебры. Пути минимизации логических функций. контрольная работа [62,8 K], добавлен 17.05.2016
Анализ и решение логических задач с помощью ЭВМ. Умение рассуждать как сущность логики. Освоение алгебры высказываний в информатике. Получение на компьютере таблицы истинности некоторого сложного выражения. Решение задач на языке программирования Паскаль. реферат [36,8 K], добавлен 29.01.2010
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Математические и логические основы информатики методичка. Программирование, компьютеры и кибернетика.
Сочинение По Картине Аркадия Пластова 1 Снег
Дипломная Работа На Тему Правотворческая Деятельность Субъектов Рф
Реферат: Еволюція релігійної філософії XX ст
Реферат по теме Вчення Ж. Бодена про державу
Реферат: Тросовые системы в космосе
Курсовая работа по теме Разработка автоматизированного рабочего места помощника бухгалтера ООО 'Торговый дом 'Алдан''
Реферат: Вплив алкоголю на організм людини
Реферат: Panama Canal Essay Research Paper PANAMA CANALThe
Меры административного принуждения
Контрольная Работа 2 По Алгебре Ответы
Доклад по теме Голубика
Контрольная Работа 9 Класс Макарычев Квадратичная Функция
Нормативно-правовое регулирование и организация аудиторской деятельности
Реферат по теме Современные ориентиры внешней и внутренней валютной политики Украины
Курсовая работа по теме Вибір цільового ринку для підприємств в сфері малого бізнесу
Доклад по теме Бизнес-план инвестиционного проекта по организации мини-фермы по доращиванию и откорму молодняка свиней КФХ И.В. Николаева в деревне Ивановка муниципального района (Бижбулякский район Республики Башкортостан)
Организация работы горячего цеха школьной столовой
Реферат: Действия по речевым сообщениям и спецобработка после воздействия РВ. Скачать бесплатно и без регистрации
Реферат: Амортизация основных фондов
Курсовая работа по теме Денежный рынок и его регулирование
Ацтеки и древние народы области Анд - История и исторические личности реферат
Операции аренды нежилого помещения - Государство и право курсовая работа
Учет и анализ использования основных средств организации - Бухгалтерский учет и аудит дипломная работа