7
$\begingroup$

I apologize if this is an under specified question, but I will try and provide some context. I am beginning to learn the foundations of propositional and predicate logic after starting a course in abstract algebra (groups, fields, rings, etc).

I find that predicate logic comes very easy to me because of its relation to set theory...the quantifiers make the whole visualization of "which elements make a statement true" very intuitive and easy to work through. However, I am struggling to find a similar feature with propositional logic (perhaps because I have been trying to mimic my strategy from predicate logic).

I understand that one can use truth tables to attack propositional logic...but the truth tables seem very...artificial and not particularly insightful.

As an example, I commonly see this picture used to explain implication if $p$ then $q$ propositions:

implication

Which, on its own, makes perfect sense. But I fail to see how this picture also represents $\neg p \lor q$, which is an equivalent form of $p \rightarrow q$. (As confirmed by truth tables)

If anything, the space "not $p$" would just be $q \land \neg p$...and therefore $\neg p \lor q$ would just be $(q \land \neg p) \lor q$...which is just $q$. But that means that $p \rightarrow q = q$...and that cannot be right, can it? That's sort of like modus ponens but missing the second step of decalring that $p$ is true.

Regardless, I'm clearly not thinking about this subject in an effective way so if anyone can offer insight, I'd greatly appreciate it!

Edit: I am adding some pictures to clarify some confusion:

Answers offered below have made me realize that the picture previously provided is incomplete. There should exist another set, call it $E$ (for Everything) that contains, in addition to q, everything outside of q. This changes my understanding of what $\neg p$ means...but questions nonetheless remain.

$\neg p$ and $q$ are therefore illustrated as follows:

not p and q within E illustration

Therefore, $\neg p \lor q$ looks like this:

everything true

To me this means that every element in the universe satisfies the proposition of $\neg p \lor q$...which by equivalence, means that every element in the universe satisfies the proposition $p \rightarrow q$. Could I have further clarification?

$\endgroup$
  • $\begingroup$ One should not visualise propositional logic to begin with. $\endgroup$ – Asaf Karagila Aug 8 at 10:31
  • $\begingroup$ @AsafKaragila could you...elaborate? Why, for example, would you not advocate for NoahScweber's approach? (one of the answers below) $\endgroup$ – S.Cramer Aug 8 at 11:11
  • 1
    $\begingroup$ Because relying on visualization will help you understand, at most, just the simplest things. And sure, it's important, but nothing useful is simple. And developing intuition based on the definition is far more important. And for this, it is often better to avoid visualizations altogether. $\endgroup$ – Asaf Karagila Aug 8 at 11:13
6
$\begingroup$

A propositional sentence, built out of propositional atoms, does indeed describe a set: namely, the set of valuations making it true. Remember that a valuation is just a map from the set of atoms to $\{$True, False$\}$ (such a map extends to a map from the set of all propositional sentences to $\{$True, False$\}$ via an appropriate recursion). Valuations in propositional logic serve the same semantic role as models in predicate logic: a propositional sentence is true, or false, with respect to a given valuation, and different valuations make different things true or false.

For $\varphi$ a propositional sentence, let $Set(\varphi)$ be the set of valuations making $\varphi$ true. Think of $Set(\varphi)$ as describing the conditions under which $\varphi$ is true: a smaller set corresponds to a more demanding sentence. For example, suppose I have two sentences, $\varphi$ and $\psi$. Then we have $$Set(\varphi\implies\psi)=Set(\neg\varphi)\cup Set(\psi),$$ since a valuation satisfies $\varphi\implies \psi$ iff it either satisfies $\neg\varphi$ or it satisfies $\psi$.

Note that this means that the Boolean propositional operations (conjunction, disjunction, negation, ...) correspond as desired to Boolean set operations (intersection, union, (relative) complementation, ...). So this does indeed give a set-theoretic interpretation of propositional logic.


Now let's look at Venn diagrams.

Venn diagrams are visual representations of the $Set(-)$ operation - or rather, they are a pictorial language for making assertions about the valuation sets assigned to propositional sentences. E.g. when we draw one circle wholly inside another, we're asserting that every valuation making the first circle's sentence true also makes the second circle's sentence true. Crucially, a "point on the plane" in a Venn diagram represents a valuation.

Keep in mind that the assertion made by a specific diagram may or may not be correct - it's always possible to write something meaningful but wrong.

But suppose I've gone ahead and done that: I have two propositional sentences $\varphi$ and $\psi$, and I've drawn circles $C_\varphi$ and $C_\psi$ representing them each respectively, and I've drawn $C_\varphi$ wholly inside $C_\psi$. That drawing is correct iff every valuation making $\varphi$ true also makes $\psi$ true. That statement in turn is true iff there are no valuations which make $\varphi$ true but $\psi$ false, and that statement's truth is equivalent to the claim that $(\neg\varphi)\vee\psi$ is true under every valuation - and that in turn is the assertion made by the Venn diagram which represents $(\neg\varphi)\vee\psi$ as everything.

$\endgroup$
  • $\begingroup$ This is exactly what I was looking for. Do you happen to know of any books that teach this material in the manner with which you just described it? I’ve been trying to figure out the lowest level of logic and this seems to be at least nearing it. $\endgroup$ – S.Cramer Aug 8 at 2:56
  • 1
    $\begingroup$ @S.Cramer Sorry, I just saw this. No, I don't know of such a text - this is something I learned from in-person conversations and/or pieced together myself over time. $\endgroup$ – Noah Schweber Oct 12 at 20:27
5
$\begingroup$

If anything, the space "not $p$" would just be $q$.

No, $\lnot p$ is the region outside the inner disc — that is everything that is not inside the inner disc – which includes part of the outer disc and everything outside of it.

$q$ is the region inside the outer disk.

$\lnot p\vee q$ is the union of both regions, which we are claiming is everything.   The diagram agrees, since at least one of the following statements is guaranteed for any point at all: (1) it is not on the inner disc, or (2) it is on the outer disc.

  • Any point on the inner disc is on the outer disc (it is $q$).
  • Any point outside both disc is not on the inner disc (it is $\lnot p$).
  • Any point between is both.
  • That covers all points on the diagram; so it matches the claim: $\lnot p\lor q$ .

And of course, if a point is on the inner disc, then it is on the outer disc. (The inner disc is a subset of the outer disc.)   Thus the diagram corresponds to $p\to q$ too.

$\endgroup$
  • $\begingroup$ Oh, sorry about that. I meant to say q complement p. I’ll make the edit. Nonetheless, doesn’t “q complement p OR q” still equal q? $\endgroup$ – S.Cramer Aug 8 at 2:26
  • 1
    $\begingroup$ "q complement p OR q" is not a well formed statement. Are you aiming for the equivalent of set difference? Because, indeed, $(q\land\lnot p)\lor q = q$ (in general, not just on this diagram). $\endgroup$ – Graham Kemp Aug 8 at 2:29
  • $\begingroup$ Do complements not exist in propositional logic? $\endgroup$ – S.Cramer Aug 8 at 2:31
  • $\begingroup$ Ohhhh, so even if I had written it as the set difference, I would have been wrong. I am not factoring in what exists “outside the boundary” of q. Got it! $\endgroup$ – S.Cramer Aug 8 at 2:35
  • 1
    $\begingroup$ The analogue for complement is negation. The analogue of relative complement (aka set difference*) is conjunction with a negation $(q\land\lnot p)$. $\endgroup$ – Graham Kemp Aug 8 at 2:35
1
$\begingroup$

I find $A\implies B\space \equiv \space \neg (A \land \neg B)\space$ to be a more intuitive definition.

If you want to visualize $A$ and $B$ as sets, you can use a Venn diagram that excludes only those elements of $A$ (left circle) that are not also elements of $B$ (right circle).

enter image description here

$x\in A \implies x\in B$

(Diagram from https://en.wikipedia.org/wiki/Material_conditional )

Note that all elements of $B$ satisfy this conditional relationshipship. So do all elements not in $A$.

You shouldn't depend too much on such diagrams, however. They are useful only for the most simple cases and won't be accepted as a valid proof in any advanced courses.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.