Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Propositional formula
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
=== Memory === [[File:Propositional formula flip flops 1.png|400px|thumb|right| About the simplest memory results when the output of an OR feeds back to one of its inputs, in this case output "q" feeding back into "p". The next simplest is the "flip-flop" shown below the once-flip. Analysis of these sorts of formulas can be done by either cutting the feedback path(s) or inserting (ideal) delay in the path. A cut path and an assumption that no delay occurs anywhere in the "circuit" results in inconsistencies for some of the '''total states''' (combination of inputs and outputs, e.g. (p=0, s=1, r=1) results in an inconsistency). When delay is present these inconsistencies are merely '''transient''' and expire when the delay(s) expire. The drawings on the right are called [[state diagram]]s.]] [[File:Propositional formula 3.png|400px|thumb|right| A "clocked flip-flop" memory ("c" is the "clock" and "d" is the "data"). The data can change at any time when clock c=0; when clock c=1 the output q "tracks" the value of data d. When c goes from 1 to 0 it "traps" d = q's value and this continues to appear at q no matter what d does (as long as c remains 0).]] Without delay, inconsistencies must be eliminated from a truth table analysis. With the notion of "delay", this condition presents itself as a momentary inconsistency between the fed-back output variable q and p = q<sub>delayed</sub>. A truth table reveals the rows where inconsistencies occur between p = q<sub>delayed</sub> at the input and q at the output. After "breaking" the feed-back,<ref>McKlusky p. 194-5 discusses "breaking the loop" and inserts "amplifiers" to do this; Wickes (p. 118-121) discuss inserting delays. McCluskey p. 195ff discusses the problem of "races" caused by delays.</ref> the truth table construction proceeds in the conventional manner. But afterwards, in every row the output q is compared to the now-independent input p and any inconsistencies between p and q are noted (i.e. p=0 together with q=1, or p=1 and q=0); when the "line" is "remade" both are rendered impossible by the Law of contradiction ~(p & ~p)). Rows revealing inconsistencies are either considered [[transient state]]s or just eliminated as inconsistent and hence "impossible". ==== Once-flip memory ==== About the simplest memory results when the output of an OR feeds back to one of its inputs, in this case output "q" feeds back into "p". Given that the formula is first evaluated (initialized) with p=0 & q=0, it will "flip" once when "set" by s=1. Thereafter, output "q" will sustain "q" in the "flipped" condition (state q=1). This behavior, now time-dependent, is shown by the [[state diagram]] to the right of the once-flip. {| |- style="font-size:9pt" align="center" ! width="16.5" Height="12" | ! width="14.25" | ! width="14.25" | ! width="14.25" | ! style="background-color:#FDE9D9;font-weight:bold" width="14.25" | q ! width="14.25" | ! width="14.25" | ! width="23.25" | ! width="153" | |- style="font-size:9pt" align="center" ! style="font-weight:bold" Height="12" | p ! style="font-weight:bold" | s ! style="font-weight:bold" | ( ! style="background-color:#FCFF7F;font-weight:bold" | s ! style="background-color:#FDE9D9;font-weight:bold" | ∨ ! style="font-weight:bold" | p ! style="font-weight:bold" | ) ! style="background-color:#FDE9D9;font-weight:bold" | = q ! |- style="font-size:9pt" align="center" | Height="12" | 0 | 0 | | 0 |style="background-color:#FDE9D9" | 0 | 0 | |style="background-color:#FDE9D9" | 0 | state 0, s=0 |- style="font-size:9pt" align="center" |style="background-color:#BFBFBF" Height="12" | 0 |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | 1 |style="background-color:red" | 1 |style="background-color:red" | 0 |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#D8D8D8" | q & p inconsistent |- style="font-size:9pt" align="center" | Height="12" | 1 | 0 | | 0 |style="background-color:#FDE9D9" | 1 | 1 | |style="background-color:#FDE9D9" | 1 | state 1 with s = 0 |- style="font-size:9pt" align="center" | Height="12" | 1 | 1 | |style="background-color:#FCFF7F" | 1 |style="background-color:#FDE9D9" | 1 | 1 | |style="background-color:#FDE9D9" | 1 | state 1 with s = 1 |} ==== Flip-flop memory ==== The next simplest case is the "set-reset" [[Flip-flop (electronics)|flip-flop]] shown below the once-flip. Given that r=0 & s=0 and q=0 at the outset, it is "set" (s=1) in a manner similar to the once-flip. It however has a provision to "reset" q=0 when "r"=1. And additional complication occurs if both set=1 and reset=1. In this formula, the set=1 ''forces'' the output q=1 so when and if (s=0 & r=1) the flip-flop will be reset. Or, if (s=1 & r=0) the flip-flop will be set. In the abstract (ideal) instance in which s=1 β s=0 & r=1 β r=0 simultaneously, the formula q will be indeterminate (undecidable). Due to delays in "real" OR, AND and NOT the result will be unknown at the outset but thereafter predicable. {| |- style="font-size:9pt" align="center" ! width="19.5" Height="12" | ! width="19.5" | ! width="19.5" | ! width="14.25" | ! width="14.25" | ! style="background-color:#FDE9D9;font-weight:bold" width="14.25" | q ! width="14.25" | ! width="14.25" | ! width="16.5" | ! width="14.25" | ! width="14.25" | ! width="14.25" | ! width="14.25" | ! width="14.25" | ! width="14.25" | ! width="23.25" | ! width="153" | |- style="font-size:9pt" align="center" ! style="font-weight:bold" Height="12" | p ! style="font-weight:bold" | s ! style="font-weight:bold" | r ! style="font-weight:bold" | ( ! style="background-color:#FCFF7F;font-weight:bold" | s ! style="background-color:#FDE9D9;font-weight:bold" | ∨ ! style="font-weight:bold" | ( ! style="font-weight:bold" | p ! style="background-color:#DBE5F1;font-weight:bold" | & ! style="background-color:#EAF1DD;font-weight:bold" | ~ ! style="font-weight:bold" | ( ! style="background-color:#FCFF7F;font-weight:bold" | r ! style="font-weight:bold" | ) ! style="font-weight:bold" | ) ! style="font-weight:bold" | ) ! style="background-color:#FDE9D9;font-weight:bold" | = q ! |- style="font-size:9pt" align="center" | Height="12" | 0 | 0 | 0 | | 0 |style="background-color:#FDE9D9" | 0 | | 0 |style="background-color:#DBE5F1" | 0 |style="background-color:#EAF1DD" | 1 | | 0 | | | |style="background-color:#FDE9D9" | 0 | state 0 with ( s=0 & r=0 ) |- style="font-size:9pt" align="center" | Height="12" | 0 | 0 | 1 | | 0 |style="background-color:#FDE9D9" | 0 | | 0 |style="background-color:#DBE5F1" | 0 |style="background-color:#EAF1DD" | 0 | |style="background-color:#FCFF7F" | 1 | | | |style="background-color:#FDE9D9" | 0 | state 0 with ( s=0 & r=1 ) |- style="font-size:9pt" align="center" |style="background-color:#D8D8D8" Height="12" | 0 |style="background-color:#D8D8D8" | 1 |style="background-color:#D8D8D8" | 0 |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | 1 |style="background-color:red" | 1 |style="background-color:#D8D8D8" | |style="background-color:red" | 0 |style="background-color:#D8D8D8" | 0 |style="background-color:#D8D8D8" | 1 |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | 0 |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | q & p inconsistent |- style="font-size:9pt" align="center" |style="background-color:#D8D8D8" Height="12" | 0 |style="background-color:#D8D8D8" | 1 |style="background-color:#D8D8D8" | 1 |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | 1 |style="background-color:red" | 1 |style="background-color:#D8D8D8" | |style="background-color:red" | 0 |style="background-color:#D8D8D8" | 0 |style="background-color:#D8D8D8" | 0 |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | 1 |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | q & p inconsistent |- style="font-size:9pt" align="center" | Height="12" | 1 | 0 | 0 | | 0 |style="background-color:#FDE9D9" | 1 | | 1 |style="background-color:#DBE5F1" | 1 |style="background-color:#EAF1DD" | 1 | | 0 | | | |style="background-color:#FDE9D9" | 1 | state 1 with ( s=0 & r=0 ) |- style="font-size:9pt" align="center" |style="background-color:#D8D8D8" Height="12" | 1 |style="background-color:#D8D8D8" | 0 |style="background-color:#D8D8D8" | 1 |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | 0 |style="background-color:red" | 0 |style="background-color:#D8D8D8" | |style="background-color:red" | 1 |style="background-color:#D8D8D8" | 0 |style="background-color:#D8D8D8" | 0 |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | 1 |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | |style="background-color:#D8D8D8" | q & p inconsistent |- style="font-size:9pt" align="center" | Height="12" | 1 | 1 | 0 | |style="background-color:#FCFF7F" | 1 |style="background-color:#FDE9D9" | 1 | | 1 |style="background-color:#DBE5F1" | 1 |style="background-color:#EAF1DD" | 1 | | 0 | | | |style="background-color:#FDE9D9" | 1 | state 1 with ( s=1 & r=0 ) |- style="font-size:9pt" align="center" |style="background-color:#F2F2F2" Height="12" | 1 |style="background-color:#F2F2F2" | 1 |style="background-color:#F2F2F2" | 1 |style="background-color:#F2F2F2" | |style="background-color:#FCFF7F" | 1 |style="background-color:#FDE9D9" | 1 |style="background-color:#F2F2F2" | |style="background-color:#F2F2F2" | 1 |style="background-color:#DBE5F1" | 0 |style="background-color:#EAF1DD" | 0 |style="background-color:#F2F2F2" | |style="background-color:#FCFF7F" | 1 |style="background-color:#F2F2F2" | |style="background-color:#F2F2F2" | |style="background-color:#F2F2F2" | |style="background-color:#FDE9D9" | 1 |style="background-color:#F2F2F2" | state 1 with s & r simultaneously 1 |} ==== Clocked flip-flop memory ==== The formula known as "clocked flip-flop" memory ("c" is the "clock" and "d" is the "data") is given below. It works as follows: When c = 0 the data d (either 0 or 1) cannot "get through" to affect output q. When c = 1 the data d "gets through" and output q "follows" d's value. When c goes from 1 to 0 the last value of the data remains "trapped" at output "q". As long as c=0, d can change value without causing q to change. * Examples *# ( ( c & d ) ∨ ( '''p''' & ( ~( c & ~( d ) ) ) ) = '''q''', but now let p = q: *# ( ( c & d ) ∨ ( '''q''' & ( ~( c & ~( d ) ) ) ) = '''q''' The state diagram is similar in shape to the flip-flop's state diagram, but with different labelling on the transitions. {| |- style="font-size:9pt" ! width="26.25" Height="12" align="center" | ! width="16.5" align="center" | ! width="16.5" align="center" | ! width="16.5" align="center" | ! width="10.5" align="center" | ! width="10.5" align="center" | ! width="10.5" align="center" | ! style="background-color:#DBE5F1" width="10.5" align="center" | s ! width="10.5" align="center" | ! width="10.5" align="center" | ! style="background-color:#FDE9D9;font-weight:bold" width="10.5" align="center" | q ! width="10.5" align="center" | ! width="10.5" align="center" | ! style="background-color:#DBE5F1" width="10.5" align="center" | w ! style="background-color:#EAF1DD" width="10.5" align="center" | v ! width="10.5" align="center" | ! width="10.5" align="center" | ! width="10.5" align="center" | ! style="background-color:#DBE5F1" width="10.5" align="center" | r ! style="background-color:#EAF1DD" width="10.5" align="center" | u ! width="10.5" align="center" | ! width="10.5" align="center" | ! width="10.5" align="center" | ! width="10.5" align="center" | ! width="10.5" align="center" | ! width="10.5" align="center" | ! width="10.5" align="center" | ! width="17.25" align="center" | ! width="201" | |- style="font-size:9pt" align="center" ! style="background-color:#F2F2F2" Height="14.25" | row ! style="font-weight:bold" | q ! style="font-weight:bold" | d ! style="font-weight:bold" | c ! style="font-weight:bold" | ( ! style="font-weight:bold" | ( ! style="font-weight:bold" | c ! style="background-color:#DBE5F1;font-weight:bold" | & ! style="font-weight:bold" | d ! style="font-weight:bold" | ) ! style="background-color:#FDE9D9;font-weight:bold" | ∨ ! style="font-weight:bold" | ( ! style="background-color:#FDE9D9;font-weight:bold" | q ! style="background-color:#DBE5F1;font-weight:bold" | & ! style="background-color:#EAF1DD;font-weight:bold" | ~ ! style="font-weight:bold" | ( ! style="font-weight:bold" | ( ! style="font-weight:bold" | c ! style="background-color:#DBE5F1;font-weight:bold" | & ! style="background-color:#EAF1DD;font-weight:bold" | ~ ! style="font-weight:bold" | ( ! style="font-weight:bold" | d ! style="font-weight:bold" | ) ! style="font-weight:bold" | ) ! style="font-weight:bold" | ) ! style="font-weight:bold" | ) ! style="font-weight:bold" | ) ! style="background-color:#FDE9D9;font-weight:bold" | =q ! style="font-weight:bold" | Description |- style="font-size:9pt" align="center" |style="background-color:#F2F2F2;font-weight:bold" Height="12" | 0 | 0 | 0 | 0 | | | 0 |style="background-color:#DBE5F1" | 0 | 0 | |style="background-color:#FDE9D9" | 0 | |style="background-color:#FDE9D9" | 0 |style="background-color:#DBE5F1" | 0 |style="background-color:#EAF1DD" | 1 | | | 0 |style="background-color:#DBE5F1" | 0 |style="background-color:#EAF1DD" | 1 | | 0 | | | | | |style="background-color:#FDE9D9" | 0 | state 0 with ( s=0 & r=0 ), 0 is trapped |- style="font-size:9pt" align="center" |style="background-color:#F2F2F2;font-weight:bold" Height="12" | 1 | 0 | 0 | 1 | | |style="background-color:#FCFF7F" | 1 |style="background-color:#DBE5F1" | 0 | 0 | |style="background-color:#FDE9D9" | 0 | |style="background-color:#FDE9D9" | 0 |style="background-color:#DBE5F1" | 0 |style="background-color:#EAF1DD" | 0 | | |style="background-color:#FCFF7F" | 1 |style="background-color:#DBE5F1" | 1 |style="background-color:#EAF1DD" | 1 | | 0 | | | | | |style="background-color:#FDE9D9" | 0 | state 0 with ( d=0 & c=1 ):<br/>q=0 is following d=0 |- style="font-size:9pt" align="center" |style="background-color:#F2F2F2;font-weight:bold" Height="12" | 2 | 0 | 1 | 0 | | | 0 |style="background-color:#DBE5F1" | 0 | 1 | |style="background-color:#FDE9D9" | 0 | |style="background-color:#FDE9D9" | 0 |style="background-color:#DBE5F1" | 0 |style="background-color:#EAF1DD" | 1 | | | 0 |style="background-color:#DBE5F1" | 0 |style="background-color:#EAF1DD" | 0 | | 1 | | | | | |style="background-color:#FDE9D9" | 0 | state 0 with ( d=1 & r=0 ), 0 is trapped |- style="font-size:9pt" align="center" |style="background-color:#BFBFBF;font-weight:bold" Height="12" | 3 |style="background-color:#BFBFBF" | 0 |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | |style="background-color:red" | 1 |style="background-color:#BFBFBF" | |style="background-color:red" | 0 |style="background-color:#BFBFBF" | 0 |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | 0 |style="background-color:#BFBFBF" | 0 |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#D8D8D8" | q & p inconsistent |- style="font-size:9pt" align="center" |style="background-color:#F2F2F2;font-weight:bold" Height="12" | 4 | 1 | 0 | 0 | | | 0 |style="background-color:#DBE5F1" | 0 | 0 | |style="background-color:#FDE9D9" | 1 | |style="background-color:#FDE9D9" | 1 |style="background-color:#DBE5F1" | 1 |style="background-color:#EAF1DD" | 1 | | | 0 |style="background-color:#DBE5F1" | 0 |style="background-color:#EAF1DD" | 1 | | 0 | | | | | |style="background-color:#FDE9D9" | 1 | state 1 with (d =0 & c=0 ), 1 is trapped |- style="font-size:9pt" align="center" |style="background-color:#BFBFBF;font-weight:bold" Height="12" | 5 |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | 0 |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | 0 |style="background-color:#BFBFBF" | 0 |style="background-color:#BFBFBF" | |style="background-color:red" | 0 |style="background-color:#BFBFBF" | |style="background-color:red" | 1 |style="background-color:#BFBFBF" | 0 |style="background-color:#BFBFBF" | 0 |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | 1 |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | 0 |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#BFBFBF" | |style="background-color:#D8D8D8" | q & p inconsistent |- style="font-size:9pt" align="center" |style="background-color:#F2F2F2;font-weight:bold" Height="12" | 6 | 1 | 1 | 0 | | | 0 |style="background-color:#DBE5F1" | 0 | 1 | |style="background-color:#FDE9D9" | 1 | |style="background-color:#FDE9D9" | 1 |style="background-color:#DBE5F1" | 1 |style="background-color:#EAF1DD" | 1 |style="background-color:#EAF1DD" | | | 0 |style="background-color:#DBE5F1" | 0 |style="background-color:#EAF1DD" | 0 | | 1 | | | | | |style="background-color:#FDE9D9" | 1 | state 1 with (d =1 & c=0 ), 1 is trapped |- style="font-size:9pt" align="center" |style="background-color:#F2F2F2;font-weight:bold" Height="12" | 7 | 1 | 1 | 1 | | |style="background-color:#FCFF7F" | 1 |style="background-color:#DBE5F1" | 1 |style="background-color:#FCFF7F" | 1 | |style="background-color:#FDE9D9" | 1 | |style="background-color:#FDE9D9" | 1 |style="background-color:#DBE5F1" | 1 |style="background-color:#EAF1DD" | 1 | | |style="background-color:#FCFF7F" | 1 |style="background-color:#DBE5F1" | 0 |style="background-color:#EAF1DD" | 0 | |style="background-color:#FCFF7F" | 1 | | | | | |style="background-color:#FDE9D9" | 1 | state 1 with ( d=1 & c=1 ):<br/>q=1 is following d=1 |}
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)