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
4 answers

Are True or False themselves propositions?

I’ve been arguing with my dad about whether or not True and False are actually propositions themselves, and I’d be curious to hear your thoughts. The definition of a proposition I’m seeing in most places is a declarative sentence which can have a…
2
votes
1 answer

Proving law of excluded middle and double negation elimination are equivalent

I'm self-studying propositional calculus, and one of the exercises is to prove that replacing the law of excluded middle ($A \lor \lnot A$) with double negation elimination (that is, $\lnot \lnot A \rightarrow A$) does not change the set of provable…
0xd34df00d
  • 1,801
2
votes
0 answers

Can propositional calculus be written with a single rewrite rule?

I have seen some systems where propositional logic can be written by a single axiom plus an inference rule such as Nicod's axiom. This to me seems like two rewrite rules. If Nicod's axiom is $N(a,b,c,d)$ then any statements $a\land b\land c\land d…
zooby
  • 4,343
2
votes
3 answers

How can I calculate the number of models in which a logical sentence is true?

How can I calculate the number of models in which a logical sentence is true? Or maybe more precisely, the number of models that satisfy the logical sentence. In a knowledge base, I have 100 variables, labeled $A1,A2,...A100$ which are either $true$…
Matsemann
  • 125
2
votes
3 answers

Propositional logic: Proving contingency without truthtable

How can one proof that a proposition is a contingency? With a truth table it is easy (show that there is at least 1 true and 1 false outcome). But with rewriting propositions using logical equivalence laws this becomes a lot more difficult. Normally…
pveentjer
  • 169
2
votes
3 answers

Why are "$(P ⇒ Q) ⇒ R$" and "$P ⇒ (Q ⇒ R)$" not logically equivalent?

According to the order of precedence, why are the following not logically equivalent? $$(P ⇒ Q) ⇒ R$$ $$P ⇒ (Q ⇒ R)$$ I am confused about where brackets fit into the order of precedence.
sktsasus
  • 2,042
2
votes
3 answers

Prove $P \lor (P \land Q) \equiv P$ without using a truth table

I don't know how to solve the question above without using a truth table. If anyone could help me, that would be great! The method used should be used something like LHS and RHS.
2
votes
2 answers

Prove $[\neg p \land (p \lor q)] \to q$ is TRUE using logic laws

Prove that $$[\neg p \land (p \lor q)] \to q$$ is TRUE using logic laws. Here is how I solved it: Starting with $[\neg p \land (p \lor q)] \to q$ An understood logical equivalence $[\neg \neg p \land \neg(p \lor q)] \lor q$ Double negation $[p…
Derpm
  • 69
2
votes
1 answer

Mathematical term for "opposite" in this context?

A friend wanted to play a game where we would roll a die, and if it landed even then the wish would come true, but if it landed odd then the opposite of the wish would come true. So let's say I have five dollars and my wish is to gain five dollars.…
Veqen
  • 21
2
votes
3 answers

Is the following conditional statement: $\,(p\land q) \to p\,$ a tautology?

Is $(p\land q) \to p$ a tautology? So far I did the following $$(p\land q)\to p \equiv \lnot (p\land q)\lor p \equiv (\lnot p\lor ¬q)\lor p$$ I'm having trouble trying to show that the conditional statement above is a tautology without using a…
J.Z
  • 33
2
votes
1 answer

How to prove it: clarifications on simple Example 1.2.3

Please help to check my understanding of Example 1.2.3 from "How to prove it" by Daniel Velleman. Determine whether the following arguments are valid. Either John isn’t stupid and he is lazy, or he’s stupid. John is stupid. Therefore, John isn’t…
TohaSt
  • 21
2
votes
2 answers

How many non-equivalent formulas that use propositions p1... pn are there?

Hi I am stuck on the following question : How many non-equivalent formulas that use propositions p1...pn are there? I'm not quite sure how to find the non-equivalent formulas here, and could someone also explain why the answer is so? Any help would…
2
votes
2 answers

Proving that $p\land q$ cannot be written in terms of $p,q,\Rightarrow$

We have $p\lor q\equiv (p\Rightarrow q)\Rightarrow q$. I am trying to show that there is no such formula representing "$\land$". I tried showing that if we could, we would then be able to deduce $\bot$, but without success. I also tried writing:…
K. 622
  • 923
2
votes
5 answers

Assume that $a \implies \text{false}$. What does that imply about $a$?

The title says most of it. I've recently started learning logical implications, and in my homework I stumbled upon a task that states that, Assume that $a\implies\text{false}$. What does that imply about $a$? I tried looking up this problem…
August
  • 99
2
votes
1 answer

Prove that two propositions $φ$ and $ψ$ are syntactically equivalent if and only if the proposition $φ↔ψ$ is a tautology

$φ↔ψ$ is a tautology. Does it mean $φ↔ψ$ is always true? If so, then we can derive $φ\rightarrowψ$ and $φ\leftarrowψ$. But we have to prove $φ⊢ψ$ and $ψ⊢φ$. What's the difference?
yashirq
  • 505