АЛФ-ны Квайна-Мак-Класки әдісімен минимизациялау

Жалпы жағдайда құрылғы n кірістен және m шығыстан тұруы мүмкін. m=1 жағдайында біршығысты схема орын алады, қарсы жағдайда көп шығысты схема қалыптасады.

Құрылғы кірісіне {Х}кіріс алфавитінен тұратын кіріс сөздері келіп түседі, ал шығыста {У}шығыс алфавитінен тұратын шығыс сөздері болады. n кіріс және m шығыс кезінде, кіріс сөзі n шамасын құраса, шығыс сөзі m шамасын құрайды.

Егер құрылғы жұмысы t_i моментте толығымен t_i уақыт мезетінде келіп түскен кіріс сөзбен анықталатын болса, онда мұндай құрылғыны комбинациялық схема немесе жады құрылғысы жоқ ақырғы автомат деп атайды. Жадысы жоқ ақырғы автомат қарапайым логикалық құрылғы болып табылады, және олардың жұмысы бульдік өрнектермен баяндалады.

Комбинациялық схемаларды жобалау кезінде оларды синтездеу және анализдеу есептерін қарастыруға тура келеді. Комбинациялық схемаларды синтездеу этаптары:

- физикалық баяндамасы бойынша математикалық баяндамасы жасалынады (бульдік теңдеулер жүйесі);

- математикалық баяндалуы бойынша алдын ала минимизация есептерін шеше отырып, логикалық схеманы құрайды;

- логикалық схема бойынша функционалдық схема құрайды.

Комбинациялық схемаларды анализдеу барысында синтездеу процесіне қарама қарсы есептер орындалады, яғни қолда бар комбинациялық схема бойынша оның математикалық моделін жасау керек. Сонымен комбинациялық схемаларды синтездеу мәселесін шеше отырып, бульдік функцияларды шешу мәселесі де шешіледі. Бульдік функцияларды іске асырудың негізі болып логикалық элементтер саналады. Екі тұрақты күйі бар элементтер логикалық элементтер (немесе ауыспалы элементтер) деп аталады, «0» - ауыспалы элементтің (триггердің, реленің, магниттік жүрекшенің) бір күйі, «1» - екінші күйі.

Бульдік айнымалылар және функциялар логикалық элементтердің кіріс және шығыс сигналдарының мәнін бейнелейді.

Бульдік өрнектерге сәйкес біріккен олар логикалық ауыспалы схемаларды құрайды. Минимальді бульдік өрнектер кезінде минимальді комбинациялық схемалар алынады. Минимальді комбинациялық схема жоғары сенімділікпен, минимальді бағамен, жоғары жылдамдықпен сипатталады. Сондықтан комбинациялық схемаларды синтездеу мәселесін шешу барысында алгебра логика функцияларын минимизациялау мәселесін назар аудару керек. АЛФ минимизациялаудың бірнеше әдістері бар: Квайна Мак-Класки, Вейча – Карно және т.б. бірақ бұл аталған әдістер негізінде элементарлы және көршілес конъюнкцияларды жабыстыру және жұту әдістерін қолданып, бастапқы ДЖҚФ функциясы бойынша оның минимальді ДМҚФ алу болып табылады.

х₁^a1х₂^a2... х_n^an конъюнкциясы элементарлы болып саналады, егер ондағы әрбір айнымалы бір реттен артық кездеспейді, мұнда

ì _i, если a_i=0

x_i^ai = í

î x_i, если a_i=1

Конъюнкцияны қалыптастыратын әріптер саны (r) ранг деп аталады. Бірдей рангілі екі элементарлы конъюнкция көршілес деп аталады, егер олар бір аргументтің функциялары болып саналса және аргументтердің біреуі тек терістеу (инверсия) таңбасымен ғана өзгешеленсе.

r рангілі көршілес конъюнкциялардың дизъюнкциясын бастапқы конъюнкцияның ортақ бөлігі болып табылатын элементарлы r-1 рангті конъюнкциямен алмастыруға болады (жабыстыру ережесі). Мысалы, У=х₁х₂ Úх₁х₂x₃=х₁x₂.