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
1
vote
1 answer

How to formalise this English sentence in a conditional statement

Let $p$ be the proposition “I will practice more in Discrete Structure Course” and $q$ be the proposition “I will get an A+ in this course”. Express each of these as a combination of $p$ and $q$. To get an A+ in this course, it is necessary for…
gbzi
  • 21
1
vote
1 answer

Simplify $\neg p \lor \neg(q \land r)$

How can I simplify the following logical expression by using the laws of logic? $$\neg p\lor\neg(q\land r)$$ The answer given by my tutor is $q$ but it seems I can't figure out how to simplify it.
Fafau
  • 11
1
vote
1 answer

Why is $\neg (p \land q)$ different than $(\neg p \land \neg q)$?

Why is $\neg (p \land q)$ different than $(\neg p \land \neg q)$? If we let: p: Blair is a liar q: Bush is a liar Then: ¬(p & q) is "Neither Bush nor Blair are liars" which seems to be the same as: (¬p & ¬q) "Bush is not a liar and Blair is…
Andy
  • 331
1
vote
1 answer

Propositional logic: subjective statements

A) The coffee can is empty. B) I'm feeling good today. Are these sentences statements in the sense that they are true or false and never true and false at the same time? Does it matter that they are subjective(or in A) situational) and there is no…
SAJW
  • 1,327
1
vote
2 answers

Proving equivalence of $(P \Rightarrow Q) \land (Q \Rightarrow P) \equiv (P \lor Q) \Rightarrow (P \land Q)$

I am a little stymied by the following:$\def\imp{\Rightarrow}$ $(P \imp Q) \land (Q \imp P) \equiv (P \lor Q) \imp (P \land Q)$ Working with the RHS I have: $\neg(P \lor Q) \lor (P \land Q) $ $( \neg (P \lor Q) \lor P) \land (\neg (P \lor Q) \lor…
1
vote
3 answers

alternative rule for negation introduction

I have the standard rule for negation introduction, namely: $$\frac{P\Rightarrow Q\quad P\Rightarrow\neg Q}{\neg P}\quad\text{[Proof by negation]}$$ Now I need a slightly different rule (I'm not sure whether you'd say it's stronger or…
1
vote
1 answer

In classical logic ~~p -> p? Intuitionistic?

Is the following rule applicable in classical propositional logic? $\sim (\sim p)\rightarrow p$ In my textbook, it shows that $p \rightarrow\sim(\sim p)$ holds for intuitionistic logic but I was wondering if the converse of that implication was also…
ylun
  • 184
1
vote
4 answers

Showing that $(A \land B)' \land (C' \land A)' \land (C \land B')' \to A'$ without a truth table

Problem: Prove that $(A \land B)' \land (C' \land A)' \land (C \land B')' \to A'$. What I have done so far: $(A \land B)'$ premise $(C' \land A)'$ premise $(C \land B')'$ premise $A' \lor B'$ 1, De Morgan $C \lor A'$ 2, De Morgan $C' \lor B$ 3,…
1
vote
1 answer

logic: derive a formula using laws

Let's say I have the following formula: $$(A\wedge\neg C)\vee(B\wedge C)\vee(A\wedge B).\tag{1}$$ It is easy to show following: $$(A\wedge\neg C)\vee(B\wedge C)\vee(A\wedge B)\Leftrightarrow (A\wedge\neg C)\vee(B\wedge C).$$ What about deriving…
Ivan
  • 53
1
vote
2 answers

What will the declarative sentence No shoes, no shirt, no service be in propositional logic?

I need to write the following declarative sentence in propositional logic. No shoes, no shirt, no service. My solution is: ~p,~q, ~r , is it correct or do i need to use implication -> instead
1
vote
1 answer

If the TV is not on sale, I will not buy it?

If the TV is on sale, I will buy the TV. The TV is not on sale. $\therefore$ I will not buy the TV. $p$: The TV is on sale. $q$: I will buy the TV. First statement above: $p\implies q$ Second statement above: $\lnot p$ Third statement: $\lnot…
1
vote
1 answer

which of the following are valid propositions?

Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE? 1.((∀x(P(x) ∨ Q(x)))) ⟹ ((∀xP(x)) ∨ (∀xQ(x))) 2.(∀x(P (x) ⟹ Q (x))) ⟹ ((∀xP(x)) ⟹ (∀xQ(x))) 3.(∀x(P(x)) ⟹ ∀x (Q(x))) ⟹ (∀x(P(x) ⟹ Q(x))) 4.(∀x(P(x)) ⇔ (∀x…
radhika
  • 361
1
vote
1 answer

proof of Generalized De Morgan's Laws by mathematical induction

Mathematical induction: Prove the following Generalized De Morgan's Laws. $\sim({p_1\land p_2 \land \cdots \land p_n}) \iff \sim{p_1}\lor\sim{p_2}\lor\cdots\lor\sim{p_n}$ My attempt: I'll use mathematical induction for the proof: If p(n) is a…
buzzee
  • 1,530
1
vote
0 answers

Converting equivalence to CNF

I have the following scenario which I need to represent in CNF: we have $n$ bins, and $A_{ij}$ holds iff balls $i$ and $j$ are in a consecutive pair of bins such that the first bin of the pair is even-numbered. Let $B_{ik}$ denote that ball $i$ is…
Brandon
  • 465
  • 4
  • 15
1
vote
2 answers

Simplifying boolean algebra expression that contains XOR

How can I simplify followed boolean algebra expression; Normally I express as simplify without XOR also this expression contains both XOR and multiple variables. (((A + B)' * C') xor ((A' + B') * C')' ) * A