Questions tagged [propositional-calculus]

Appropriate for questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions. Also for general questions about the propositional calculus itself, including its semantics and proof theory. Questions about other kinds of logic should use a different tag, such as (logic), (predicate-logic), or (first-order-logic).

Propositional logic is a branch of logic dealing with logical connectives and statements involving them. A logical connective connects finitely many sentences and forms a compound sentence, in a way that the truth value of the compound sentence depends only on the truth value of its constituents. The most common connectives are the binary connectives conjunction ($\land$), disjunction ($\lor$) and implication ($\rightarrow$), the unary connective negation ($\neg$), and the nullary connectives true ($\top$) and false ($\bot$).

Any proposition is considered to be either atomic (in which case it has no constituents) or compound (in which case it's formed by mean a connective using simpler propositions). A propositional model is a function assigning to each atomic proposition a truth value $0$ or $1$. The truth values of compound propositions are then determined by the truth values of their constituents. For example, if $I$ is a function assigning truth values to propositions, one would have $I(\top)=1$, $I(\bot)=0$, $I(\neg A)=1-I(A)$, $I(A\land B)=\min\big(I(A),I(B)\big)$, $I(A\lor B)=\max\big(I(A),I(B)\big)$ and $I(A\rightarrow B)=\max\big(1-I(A),I(B)\big)$. The propositions having the value $1$ for every model, are called tautologies, and those having the value $0$ for every model, are called absurdities. A central task of propositional logic is characterizing tautologies and absurdities.

5541 questions
2
votes
1 answer

Verify $\neg (Q \rightarrow (P \lor Q ) ) $ is a falsehood by deduction

This is the definition of $ \bf PL $ Let $ S = S _ { \bf PL } $, the set of logical symbols for $ \bf PL $, be the union of the following three sets: $ Con = \{ \neg , \lor , \land , \rightarrow , \leftrightarrow \} $ is the set of connectives; $…
yashirq
  • 505
2
votes
2 answers

Tautologies in Boolean formulas using the bi-conditional connective

How can I prove a formula $\phi$ written using only the bi-conditional connective $\leftrightarrow$ (besides variables and parentheses) is a tautology if and only if every variable in $\phi$ occurs an even number of times? I have attempted to prove…
user378364
2
votes
4 answers

Using Logic Laws to prove $p \leftrightarrow q \equiv (p\lor q)\to(p \land q)$

I am trying to prove that $p \leftrightarrow q \equiv (p\lor q)\to(p \land q)$ and am really lost in the steps to solve this. So far I have: $p \leftrightarrow q \equiv (p\to q)\land(q\to p) \qquad$|equivalence $p \leftrightarrow q\equiv (\neg…
2
votes
1 answer

Disjunctive Normal Form for Fuzzy Logic

I'm asked to prove that every propositional assertion in Fuzzy Logic, expressed using the standard propositional connectives $\{\land, \lor,\lnot, \rightarrow, \leftrightarrow\} $ can be expressed in Disjunctive Normal Form (DNF). I want to prove by…
J.R.CD
  • 57
2
votes
1 answer

Entails Propositional Logic

Is the following statement correct? if $ \alpha \models (\beta \vee \gamma) $ then $ \alpha \models \beta \vee \alpha \models \gamma $ or both. I guess it is, but how would you prove it?
Piotr
  • 21
2
votes
2 answers

Derive hypothesis in Propositional logic

I am learning to derive proofs of some sentences based on logical axiom schemes and inference rules. But there is a lot of unclear moments, like getting hypothesis. The one such example would be $A \Rightarrow B$ and I take $A$ and will use DT. Than…
Timotei
  • 21
2
votes
1 answer

Need help with propositional logic [Proof]

I need help with proving $\neg a \vee b$ is logically equivalent to $$ \neg (((a \vee b) \wedge \neg (a \wedge b)) \wedge (a \vee ~b)) $$ by using logical equivalence law. I have tried multiple times but I can't seem to simplify them further than…
2
votes
3 answers

Does the => truth table break mathematical induction?

Since $F \Rightarrow F$ and $F \Rightarrow T$ both evaluate to $T$ with the truth table for $\Rightarrow$, does this not break mathematical induction? For example, once you show the base case holds for a proposition $P$, then you could do the…
2
votes
1 answer

Absorption Law with Negation

Would absorption law work for statements with neagations in them like $( \neg q \land \neg r) \lor r$?
1
vote
1 answer

propositional-calculus/logic riddle

Two physicists, A and B, and a logician C, are wearing hats, which they know are either black or white but not all white. A can see the hats of B and C; B can see the hats of A and C; C is blind. Each is asked in turn if they know the color of their…
1
vote
2 answers

Show that (p→q)→(r→s) and (p→r)→(q→s) are not logically equivalent.

This is a problem in my math book, however, the answer is in the back of the book as it is an odd. What I don't understand, is the fact that if I plugin r = T and p,q,s = F I end up with... (F→F)→(T→F) (F→T)→(F→F) T→F T→T …
1
vote
1 answer

Propositional Calculus : Showing $\{ \lnot, \# \}$ is not complete

Let the ternary connective $ \# $ stand for the majority connective. Accordingly, the truth value of $ (\# p q r) $ is $T$ if a majority of $p, q, r$ are true. $(\#pqr)$ is false if a majority of $p, q, r$ is false. I am having trouble to prove:…
Ishfaaq
  • 10,034
  • 2
  • 30
  • 57
1
vote
3 answers

prove validity of following sequent

How to prove validity of following sequent using rules of conjunction, disjunction, implication, negation etc. Premises: $ c \wedge n \Rightarrow t$ , $h \wedge \sim s$, $h \wedge \sim(s\vee c) \Rightarrow p $ Conclusion: $ n \wedge \sim t…
Zur
  • 79
1
vote
3 answers

Propositional logic De-morgans theorem question

the theorem states that $(A\wedge B) = \neg (\neg A\vee \neg B)$, where $A$ and $B$ are propositional formulas. Can't I turn $\neg (\neg A\vee \neg B)$ to $(\neg \neg A\vee \neg \neg B)$ then cancel the double negations so its $(A\vee B)$, because…
1
vote
1 answer

It is false that if p then q.

I'm doing some homework in which I'm converting textual descriptions of logic statements to their respective symbolic representation. If one reads It is false that if p then q. I was wondering the typical representation of this. i.e. Is it ~p -> q…
Brugsen
  • 195