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

Proving $(A\wedge B) \vee (\neg A\wedge \neg B)$ from $A\leftrightarrow B$

So I'm stuck on a fitch style proof to get $(A \wedge B) \vee (\neg A \wedge \neg B)$ from $A\leftrightarrow B$. I'm not allowed to use De Morgan's or Modus Tollens for this proof. I know I have to isolate each letter but I'm not sure how to do so…
user494506
  • 13
  • 2
1
vote
1 answer

Confused about valid consequence

I don't understand why A isn't a valid consequence of (~Q) and Q=>P. I think the first line that I highlighted is the textbook's proof of why A isn't a valid consequence of (~Q) and Q=>P, since they're both true but A is false. However, on the…
1
vote
3 answers

What is this equivalent to?

$(p\vee q)$ $\wedge$ $(p\wedge q)' \equiv ? $ I wanna find what this equivalent to. So my teacher has solved this but If it's possible, wanna get a solution which i can understand easily. My idea (I mean my teacher :P): $\equiv p \vee q$ Regards!
Lan
  • 13
1
vote
1 answer

Is there any difference between $p\vdash q$ and $\vdash p\rightarrow q$?

To me it seems there's no difference and you can prove each from the other one. Having proved $\vdash p\rightarrow q$ we can get $p\vdash q$: $\;p$ --- premise $\;p\rightarrow q$ --- theorem intro $\;q$ --- $\rightarrow$ elim 1,2 and having proved…
Pooria
  • 477
1
vote
1 answer

Formalizing a logical argument

I want to formalize this reasonning Many students will be either in Hegel’s or in Schopenhauer’s lectures, if they are scheduled at the same time. And of course Schopenhauer will schedule them at the same time as Hegel’s. If Hegel’s lectures are…
tripth
  • 23
1
vote
3 answers

Is it possible to prove that $p\to q$ from these axioms and theorems?

My professor insists this is possible, I say it isn't. What say you? Certain theorems and axioms have been established or assumed. Axiom 1: $p\rightarrow {\sim y}$ Axiom 2: ${\sim q}\rightarrow r$ Theorem 1: $p\rightarrow {\sim z}$ Theorem 2:…
Dana Hill
  • 715
1
vote
5 answers

Is the following propositional logic valid?

$$P ∧ (¬P∨Q) ∧ (¬Q∨R) → R$$ Truth table method seems to be hectic. Is there any other simple approach to check ?
Jon Garrick
  • 2,624
1
vote
0 answers

Trying to prove proposition is a tautology

Possible Duplicate: Trying to show Tautology I am trying to show that this proposition is a tautology. [(p∨q)∧(p⇒r)∧(q⇒r)]⇒r It has been asked about before on site by other users. Firstly, I took the proposition to (¬p∧¬q)∨(p∧¬r)∨(q∧¬r)∨r. As…
bosra
  • 561
1
vote
1 answer

Why are conjunctions or disjunctions in propositional calculus not allowed on an infinite set of formulas?

I'm reading a text book about propositional calculus and it says that $ \bigvee_{\phi_i \in \Phi}{\phi_i} $ and $ \bigwedge_{\phi_i \in \Phi}{\phi_i} $ are not allowed, if $ \Phi $ is not finite. It does not give an explanation. Could you please…
1
vote
2 answers

Prove modus ponens for set of formulas from tautological formulation.

I have given a correct and complete calculus for propositional…
xamid
  • 258
1
vote
1 answer

Check if a proposition with a equation is true or false and then write its negation.

I have the following: Considering three propositions $S,R,Q$, write the truth table of $(R \land S) \lor (Q \Rightarrow R)$. And also check if the following proposition: $$\forall x \in \mathbb{R}, \exists y \in \mathbb{Z} \mbox{ such that }…
JB-Franco
  • 852
1
vote
1 answer

How to show that $\Gamma\vdash (\varphi\to\neg\varphi)\to\varphi$?

Problem. Let $(\mathscr{L},\vdash)$ be a logic and $\Gamma\subseteq\mathscr{L}$ be a set of formulas such that for some $\varphi\in\mathscr{L}$ we have $$\Gamma\vdash\varphi\to\neg\varphi$$ $$\Gamma\vdash\neg\varphi\to\varphi$$Then show that,…
user170039
1
vote
1 answer

Formal logic proof using 19 rules of inference

I am working on a problem in logic. The proof is supposed to involve only 19 rules of inference. The problem is: Given: $$ Z \implies A $$ $$ Z \lor A $$ Deduce: $$ A$$ My proof is $$ (Z \implies A) \land (Z \lor A) $$ $$ (Z \implies A) \land…
ardhajya
  • 514
1
vote
2 answers

$(A \Rightarrow B \land \neg C) \land \neg(A \Rightarrow D) \Rightarrow \neg (B \Rightarrow D \lor C)$ is tautology, contradiction, or a satisfiable?

All this step should be correct $(A \Rightarrow B \land \neg C) \land \neg(A \Rightarrow D) \Rightarrow \neg (B \Rightarrow D \lor C)$ $(\neg A \lor (B \land \neg C)) \land \neg(\neg A \lor D) \Rightarrow \neg (\neg B \lor D \lor C)$ $(\neg A \lor…
Math81
  • 77
1
vote
3 answers

If $p \to q$ and if $r \to s$, can we say that if $p \land r$ then $q \land s$?

If $p \to q$ and if $r \to s$, can we say that if $p \land r$ then $q \land s$? $p,q,r,s$ are logical statements. How can I prove it?