Conjunction
By Robert Laing
In computer programing, we meet conjunction in various forms:
as the and separator between boolean tests,
as set intersections,
as database table inner joins,
as product in 2 value algebra,
as as series statements in flow control.
By Robert Laing
Once again, lets use Stanford University dean Jennifer Widom’s basic SQL examples from her college applications data as an illustration.
Which students applied for ‘CS’ and ‘EE’? In what I’ve called copula notation, conjunction is written p ∧ q, which is a handy mnemonic that its set equivalent is P ∩ Q. That logic has a spiky version of set theory’s rounded symbol we’ll also encounter in disjunction and implication.
By Robert Laing
Which majors intersect? Lets return to Venn’s 5 relations. Here we want to check A ∩ B ≠ Ø, which is true for any of the first four relations.
We need a self-join for this query, which is a form of intersection.
SELECT DISTINCT a1.major AS A, a2.major AS B FROM apply as a1, apply as a2 WHERE a1.sid = a2.sid ORDER BY A, B; a | b ----------------+----------------
bioengineering | bioengineering
bioengineering | CS
bioengineering | EE
biology | biology
biology | CS
biology | marine biology
CS | bioengineering
CS | biology
CS | CS
CS | EE
CS | marine biology
EE | bioengineering
EE | CS
EE | EE
history | history
history | psychology
marine biology | biology
marine biology | CS
marine biology | marine biology
psychology | history
psychology | psychology
(21 rows) Note everything intersects with itself.
By Robert Laing
Relational algebra uses various bowtie symbols to describe binary operations on two tables, which are anologous to combining two sets as I’ll try to explain in this diagram.
P - Q
P ∩ Q
Q - P
P
⟗
Q
The above illustrates what relational algebra calls a full outer join which combines three parts, the inner or natural join P ⋈ Q which equates to P ∩ Q, and what this section covers, flanked by left and right antijoins P ▷ Q which equats to P - Q, and Q ▷ P which equats to Q - P.
By Robert Laing
2 Value Algebra Since conjunction is closely associated with the word and, it jarred me a bit to discover that it is logic’s equivalent of multiplication, while disjunction — commonly thought of as or — is logic’s addition, the arithmetic operator I associate with and.
Why conjunction equates to multiplication is best illustrated by its truth table:
pqp · q
111
100
010
000
Moving from binary to any number of propositions, the universal quantification symbol ∀(p) tends to be used, as in
By Robert Laing
Flow Control Yet another way to think of logic is as electrical switches, where on is true and off is false. Here conjunction is switches in series, and disjunction is switches in parallel.
p
q
r
s
If any switch in series is not on (such as switch r in the above diagram), it breaks the flow of electric current, meaning a light or whatever the circuit powers would be off.