Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Изоморфность алгебры высказываний и алгебры контактных схем



Электрическая цепь снабжена "контактами", которые могут находиться в двух состояниях: "замкнуто" (1), когда пропускают ток в цепи, и "разомкнуто" (2), когда не пропускают ток.

Итак, каждый контакт может быть либо замкнут, либо разомкнут, а в алгебре высказываний каждое высказывание может быть либо истинным, либо ложным. Здесь обнаруживается глубокое сходство между системами, состоящими из объектов различной природы. Это сходство и подсказывает возможность истолкования алгебры высказываний (2-х элементной булевой алгебры) в объектах контактных схем!

Достаточно определить:

И – 1 – замкнуто

Л – 0 – разомкнуто

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

Такое взаимно – однозначное соответствие между двумя алгебрами называется изоморфизмом, а сами эти алгебры – изоморфными (имеющими одинаковую структуру).

Мы видим, что изоморфные системы, с математической точки зрения, неразличимые объекты, хотя внешне они могут быть совершенно различными.

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

Итак, математическая логика имеет непосредственную связь с теорией проектирования ЭВМ. Поведение различных компонентов ЭВМ может быть описано с помощью логических функций и законов математической логики.

Функции ЭВМ состоят в передаче по шинам, хранении, анализе и обработке дискретной информации. Дискретной - т.е. представленной в виде двоичных кодов, набором двух цифр 0 и 1. Установленная изоморфность алгебры контактных схем (электронных схем) и алгебры логики определяет, что работа любой схемы, которая может находиться лишь в одном из 2-х состояний – "включено", "выключено", полностью подчиняется законам булевой алгебры.

Следовательно, любое преобразование информации основано на выполнении ЛОГИЧЕСКИХ операций над двоичными кодами.

Всякое устройство ЭВМ, выполняющее арифметические или логические операции, можно рассматривать как функциональный преобразователь, входными переменными (аргументами) которого являются исходное двоичное число, а выходной функцией от него — новое двоичное число, образованное в результате выполнения логических операции. При этом как входные переменные, так и выходные функции могут принимать лишь одно из двух возможных значений: 0 или 1.

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

Более сложное устройство можно построить из простых путем:

1. последовательного соединения элементов;

2. параллельного соединения (не меняет функции, поэтому, с точки зрения логики, этот тип соединения не используется);

3. перестановки входов элементов.

1-му и 3-му физическим приемам в алгебре логики соответствуют:

- принцип суперпозиции (подстановка в функцию вместо ее аргументов других функций);

- подстановка аргументов (изменение порядка записи аргументов функций или замена одних аргументов функции другими).

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

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

Над логическими переменными в алгебре логики производятся логические операции, основными из которых являются отрицание дизъюнкция, конъюнкция. Для реализации этих операций на физическом уровне используются крошечные электронные устройства, которые называются логическими элементами или ВЕНТИЛЯМИ. Дискретное устройство, реализующее одну из логических операций, называется логическим элементом (вентиль). Логический элемент (схема) может иметь один или несколько входов и один выход. Состояние выхода зависит от состояний входов, следовательно, выход можно понимать как функцию входов. (Необходимо различать, что операция – это действие, а функция – зависимость.)

Число входов логического элемента будет соответствовать числу аргументов воспроизводимой им функции. На входы поступает определенная комбинация 0 и 1, выход также дает 0 или 1, в зависимости от реализуемой функции. Обычно сигнал от 0 до 1В представляет нуль, а сигнал от 2 до 5Вединицу (позитивная логика). Итак, каждый вентиль реализует определенную логическую функцию от двузначных дискретных сигналов.

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

Всякое устройство ЭВМ, выполняющее арифметические или логичес­кие операции, можно рассматривать как функциональный преобразователь, входными переменными (аргументами) которого являются исходное двоичное число, а выходной функцией от него — новое двоичное число, образованное в результате выполнения двоичной операции. При этом как входные переменные, так и выходные функции могут принимать лишь одно из двух возможных значений: 0 или 1.

В каждом конкретном случае количество входных переменных будет различным. В простейшем случае это одна переменная х, принимающая значение 0 или 1. В общем случае таких переменных может быть n, т.е. х1, х2,..., хп. Так как каждая переменная х при этом равна 0 или 1, то для n переменных образуется множество разнообразных сочетаний или наборов входных переменных.

В алгебре логики строго доказывается, что для n переменных количество различных наборов равно 2n.

Так, для одной переменной х существует только два набора: <0> или < 1 >, так как 21 = 2; для двух переменных х12 —четыре различных набора: <0,0>, <0,1>, <1,0>, <1,1>, так как 22 = 4; для трех переменных х1, х2, х3 — восемь различных наборов, так как 23 = 8, и т.д.

Функция f (х1, х2,..., хn), определяемая на наборах входных двоичных переменных х1, х2,..., хn и принимающая в качестве возможных значений 0 или 1, называется логической функцией.

Напомним, что логическая функция имеет одну или несколько переменных и выдает результат, который зависит только от значений этих переменных. Так как булева функция от n переменных имеет только 2n возможных комбинаций значений переменных, то такую функцию можно полностью описать в таблице истинности с 2n строками. Необходимо четко уяснить, что в отличие от обычной алгебры, где есть бесконечное число функций от двух переменных, в булевой алгебре число таких функций конечно и строго определено! Сколько же их будет? Переключательная функция при каждом отдельном наборе переменных может принимать одно из двух значений: 0 или 1, следовательно, количество различных функций будет равно 2m, где m – количество наборов. Мы знаем, что количество наборов определяется по формуле m = 2n, отсюда имеем количество функций равно 22**n.

Вначале необходимо изучить элементарные логические функции, чтобы на их основе строить более сложные.





Дата публикования: 2015-10-09; Прочитано: 456 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.01 с)...