Truth table: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 3,073: | Line 3,073: | ||
T T F T |
T T F T |
||
T T T T</pre> |
T T T T</pre> |
||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
'''Also works with gojq, the Go implementation of jq''' |
|||
This entry uses a PEG ([https://en.wikipedia.org/wiki/Parsing_expression_grammar Parsing Expression Grammar]) approach |
|||
to the task. In effect, a PEG grammar for logic expressions |
|||
is transcribed into a jq program for parsing and |
|||
evaluating the truth values of such expressions. |
|||
The PEG grammar for logic expressions used here is essentially as follows: |
|||
<pre> |
|||
expr = (primary '=>' primary) / e1 |
|||
e1 = e2 (('or' / 'xor') e2)* |
|||
e2 = e3 ('and' e3)* |
|||
e3 = 'not'? primary |
|||
primary = Var / boolean / '(' expr ')' |
|||
boolean = 'true' / 'false' |
|||
</pre> |
|||
where Var is a string matching the regex ^[A-Z][a-zA-Z0-9]*$ |
|||
Notice that this grammar binds '=>' most tightly, and uses `not` as a |
|||
prefix operator. |
|||
The PEG grammar above is transcribed and elaborated in the jq function |
|||
`expr` below. For details about this approach, see for example |
|||
[[Compiler/Verifying_syntax#jq]]. That entry also |
|||
contains the jq PEG library that is referenced |
|||
in the 'include' statement at the beginning of the |
|||
jq program shown below. |
|||
====Parsing==== |
|||
<syntaxhighlight lang=jq> |
|||
include "peg"; # see [[Compiler/Verifying_syntax#Generic_PEG_Library] |
|||
def expr: |
|||
def Var : parse("[A-Z][a-zA-Z0-9]*"); |
|||
def boolean : (literal("true") // literal("false")) |
|||
| .result[-1] |= fromjson; |
|||
def primary : ws |
|||
| (Var |
|||
// boolean |
|||
// box(q("(") | expr | q(")")) |
|||
) |
|||
| ws; |
|||
def e3 : ws | (box(literal("not") | primary) // primary); |
|||
def e2 : box(e3 | star(literal("and") | e3)) ; |
|||
def e1 : box(e2 | star((literal("or") // literal("xor")) | e2)) ; |
|||
def e0 : box(primary | literal("=>") | primary) // e1; |
|||
ws | e0 | ws; |
|||
def statement: |
|||
{remainder: .} | expr | eos; |
|||
</syntaxhighlight> |
|||
====Evaluation==== |
|||
<syntaxhighlight lang=jq> |
|||
# Evaluate $Expr in the context of {A,B,....} |
|||
def eval($Expr): |
|||
if $Expr|type == "boolean" then $Expr |
|||
elif $Expr|type == "string" then getpath([$Expr]) |
|||
elif $Expr|length == 1 then eval($Expr[0]) |
|||
elif $Expr|(length == 2 and first == "not") then eval($Expr[-1])|not |
|||
elif $Expr|(length == 3 and .[1] == "or") then eval($Expr[0]) or eval($Expr[2]) |
|||
elif $Expr|(length == 3 and .[1] == "xor") |
|||
then eval($Expr[0]) as $x |
|||
| eval($Expr[2]) as $y |
|||
| ($x and ($y|not)) or ($y and ($x|not)) |
|||
elif $Expr|(length == 3 and .[1] == "and") then eval($Expr[0]) and eval($Expr[2]) |
|||
elif $Expr|(length == 3 and .[1] == "=>") then (eval($Expr[0])|not) or eval($Expr[2]) |
|||
else $Expr | error |
|||
end; |
|||
</syntaxhighlight> |
|||
====Truth Tables==== |
|||
<syntaxhighlight lang=jq> |
|||
# input: a list of strings |
|||
# output: a stream of objects representing all possible true/false combinations |
|||
# Each object has the keys specified in the input. |
|||
def vars2tf: |
|||
if length == 0 then {} |
|||
else .[0] as $k |
|||
| ({} | .[$k] = (true,false)) + (.[1:] | vars2tf) |
|||
end; |
|||
# If the input is a string, then echo it; |
|||
# otherwise emit T or F |
|||
def TF: |
|||
if type == "string" then . |
|||
elif . then "T" |
|||
else "F" |
|||
end; |
|||
# Extract the distinct variable names from the parse tree. |
|||
def vars: [.. | strings | select(test("^[A-Z]"))] | unique; |
|||
def underscore: |
|||
., (length * "_"); |
|||
</syntaxhighlight> |
|||
====Examples==== |
|||
<syntaxhighlight lang=jq> |
|||
def tests: [ |
|||
"A xor B", |
|||
"notA", |
|||
"A and B", |
|||
"A and B or C", |
|||
"A=>(notB)", |
|||
"A=>(A => (B or A))", |
|||
"A xor B and C" |
|||
]; |
|||
def tables: |
|||
tests[] as $test |
|||
| ($test | statement | .result) |
|||
| . as $result |
|||
| vars as $vars |
|||
| ($vars + [" ", $test] | join(" ") | underscore), |
|||
(($vars | vars2tf) |
|||
| ( [.[], " ", eval($result) | TF] | join(" ")) ), |
|||
"" |
|||
; |
|||
tables |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
A B A xor B |
|||
_____________ |
|||
T T F |
|||
F T T |
|||
T F T |
|||
F F F |
|||
A notA |
|||
________ |
|||
T F |
|||
F T |
|||
A B A and B |
|||
_____________ |
|||
T T T |
|||
F T F |
|||
T F F |
|||
F F F |
|||
A B C A and B or C |
|||
____________________ |
|||
T T T T |
|||
F T T T |
|||
T F T T |
|||
F F T T |
|||
T T F T |
|||
F T F F |
|||
T F F F |
|||
F F F F |
|||
A B A=>(notB) |
|||
_______________ |
|||
T T F |
|||
F T T |
|||
T F T |
|||
F F T |
|||
A B A=>(A => (B or A)) |
|||
________________________ |
|||
T T T |
|||
F T T |
|||
T F T |
|||
F F T |
|||
A B C A xor B and C |
|||
_____________________ |
|||
T T T F |
|||
F T T T |
|||
T F T T |
|||
F F T F |
|||
T T F T |
|||
F T F F |
|||
T F F T |
|||
F F F F |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |