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!
==== Produce the formula's truth table ==== Produce the formula's truth table. Number its rows using the binary-equivalents of the variables (usually just sequentially 0 through n-1) for n variables. : ''Technically, the [[propositional function]] has been reduced to its (unminimized) conjunctive normal form: each row has its minterm expression and these can be OR'd to produce the formula in its (unminimized) conjunctive normal form.'' Example: ((c & d) ∨ (p & ~(c & (~d)))) = q in conjunctive normal form is: ::: ( (~p & d & c ) ∨ (p & d & c) ∨ (p & d & ~c) ∨ (p & ~d & ~c) ) = q However, this formula be reduced both in the number of terms (from 4 to 3) and in the total count of its literals (12 to 6). {| |- style="font-size:9pt;font-weight:bold" align="center" !style="background-color:#F2F2F2" width="25.5" Height="24" | row ! Minterms ! width="21" | p ! width="21" | d ! width="21" | c ! width="10.5" | ( ! width="10.5" | ( ! width="10.5" | c ! width="10.5" | & ! width="10.5" | d ! width="10.5" | ) !style="background-color:#FDE9D9" width="10.5" | ∨ ! width="10.5" | ( ! width="10.5" | p ! width="10.5" | & ! width="10.5" | ~ ! width="10.5" | ( ! width="10.5" | ( ! width="10.5" | c ! width="10.5" | & ! width="10.5" | ~ ! width="10.5" | ( ! width="10.5" | d ! width="10.5" | ) ! width="10.5" | ) ! width="10.5" | ) ! width="10.5" | ) ! width="10.5" | ) ! {{Active}} minterms ! Formula in conjunctive normal form |- style="font-size:9pt" |style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 0 | align="center" valign="bottom" | ( ~p & ~d & ~c ) | align="center" valign="bottom" | 0 | align="center" valign="bottom" | 0 | align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 0 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 | align="center" valign="bottom" | 0 | align="center" valign="bottom" | |style="background-color:#FDE9D9" align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | 0 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 |style="background-color:#EAF1DD" align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 0 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 |style="background-color:#EAF1DD" align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | valign="bottom" | | valign="bottom" | |- style="font-size:9pt" |style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 1 | align="center" valign="bottom" | ( ~p & ~d & c) | align="center" valign="bottom" | 0 | align="center" valign="bottom" | 0 | align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 1 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 | align="center" valign="bottom" | 0 | align="center" valign="bottom" | |style="background-color:#FDE9D9" align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | 0 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 |style="background-color:#EAF1DD" align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 1 |style="background-color:#DBE5F1" align="center" valign="bottom" | 1 |style="background-color:#EAF1DD" align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | valign="bottom" | | valign="bottom" | |- style="font-size:9pt" |style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 2 | align="center" valign="bottom" | ( ~p & d & ~c ) | align="center" valign="bottom" | 0 | align="center" valign="bottom" | 1 | align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 0 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 | align="center" valign="bottom" | 1 | align="center" valign="bottom" | |style="background-color:#FDE9D9" align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | 0 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 |style="background-color:#EAF1DD" align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 0 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 |style="background-color:#EAF1DD" align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | valign="bottom" | | valign="bottom" | |- style="font-size:9pt" |style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 3 | align="center" valign="bottom" | ( ~p & d & c ) | align="center" valign="bottom" | 0 | align="center" valign="bottom" | 1 | align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 1 |style="background-color:#DBE5F1" align="center" valign="bottom" | 1 | align="center" valign="bottom" | 1 | align="center" valign="bottom" | |style="background-color:#FCD5B4" align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | 0 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 |style="background-color:#EAF1DD" align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 1 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 |style="background-color:#EAF1DD" align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | |style="background-color:#FCD5B4" align="center" | (~p & d & c) | valign="bottom" | |- style="font-size:9pt" |style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 4 | align="center" valign="bottom" | ( p & ~d & ~c ) | align="center" valign="bottom" | 1 | align="center" valign="bottom" | 0 | align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 0 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 | align="center" valign="bottom" | 0 | align="center" valign="bottom" | |style="background-color:#FCD5B4" align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | 1 |style="background-color:#DBE5F1" align="center" valign="bottom" | 1 |style="background-color:#EAF1DD" align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 0 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 |style="background-color:#EAF1DD" align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | |style="background-color:#FCD5B4" align="center" | (~p & d & c) | valign="bottom" | |- style="font-size:9pt" |style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 5 | align="center" valign="bottom" | ( p & ~d & c ) | align="center" valign="bottom" | 1 | align="center" valign="bottom" | 0 | align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 1 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 | align="center" valign="bottom" | 0 | align="center" valign="bottom" | |style="background-color:#FDE9D9" align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | 1 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 |style="background-color:#EAF1DD" align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 1 |style="background-color:#DBE5F1" align="center" valign="bottom" | 1 |style="background-color:#EAF1DD" align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" | | valign="bottom" | |- style="font-size:9pt" |style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 6 | align="center" valign="bottom" | ( p & d & ~c ) | align="center" valign="bottom" | 1 | align="center" valign="bottom" | 1 | align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 0 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 | align="center" valign="bottom" | 1 | align="center" valign="bottom" | |style="background-color:#FCD5B4" align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | 1 |style="background-color:#DBE5F1" align="center" valign="bottom" | 1 |style="background-color:#EAF1DD" align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 0 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 |style="background-color:#EAF1DD" align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | |style="background-color:#FCD5B4" align="center" | (p & d & ~c) | valign="bottom" | |- style="font-size:9pt" |style="background-color:#F2F2F2;font-weight:bold" Height="12" align="center" valign="bottom" | 7 | align="center" valign="bottom" | ( p & d & c ) | align="center" valign="bottom" | 1 | align="center" valign="bottom" | 1 | align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 0 |style="background-color:#DBE5F1" align="center" valign="bottom" | 1 | align="center" valign="bottom" | 1 | align="center" valign="bottom" | |style="background-color:#FCD5B4" align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | 1 |style="background-color:#DBE5F1" align="center" valign="bottom" | 1 |style="background-color:#EAF1DD" align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | 1 |style="background-color:#DBE5F1" align="center" valign="bottom" | 0 |style="background-color:#EAF1DD" align="center" valign="bottom" | 0 | align="center" valign="bottom" | | align="center" valign="bottom" | 1 | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | | align="center" valign="bottom" | |style="background-color:#FCD5B4" align="center" | ( p & d & c ) | valign="bottom" | |- style="font-size:9pt" | Height="16.5" valign="bottom" | | align="center" valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | |style="background-color:#FFA7A9;font-weight:bold" align="center" | q | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | | valign="bottom" | |style="background-color:#FFA7A9" align="center" | = (~p&d&c) ∨ (~p&d&c) ∨ (p&d&~c ) ∨ (p&d&c ) |}
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)