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

Exercise IV.4.6. (c) Logic for Mathematicians by Rosser $\vdash P_m \supset P_1\vee P_2\vee \cdots \vee P_n$ if $1 \leq m \leq n$.

The instructions state "using only results of Sec. 4 or earlier portions of the present exercise, prove:" We have shown already the following: (a) $\vdash P\vee Q \supset Q \vee P$ and (b) $\vdash P \supset P \vee Q$. We still haven't establish…
JimmyJackson
  • 1,517
1
vote
2 answers

What does the logical condition "implies" actually mean?

$P_n$ and $Q_n$ are propositions which has a truth value $n$ where $n \in (T,F)$ So i want to access the truth value of $P\Rightarrow Q$ So $P_T$ and $Q_T$, $(P \Rightarrow Q)_T$ $P_T$ and $Q_F$, $(P \Rightarrow Q)_F$ $P_F$ and $Q_T$, $(P…
Danxe
  • 1,695
1
vote
2 answers

How to prove $((Q \wedge ¬P) \vee (Q \wedge P)) = Q$

I cannot see any steps to this problem! Surely the answer is obvious? Is there a particular law which is used to make this statement? $$((Q \wedge ¬P) \vee (Q \wedge P)) = Q$$
1
vote
3 answers

Showing tautology without a truth table.

Show that the conditional statement is a tautology without using a truth table. $a)$ $(p \wedge q) \rightarrow p$ My suggestion would be getting rid of the implication first, so $(p \wedge q) \rightarrow p \equiv \neg(p \wedge q) \vee p$ How…
1
vote
1 answer

Consequence of compactness lemma

Let $\Gamma=\Sigma \cup \left\lbrace p_i,i\geq 1 \right\rbrace$ a countable set of propositional formulas. Assume also that for every boolean evaluation $u$ that maps every member of $\Sigma$ to true , there exists an $m$ which depends on $u$ such…
mort32
  • 13
1
vote
1 answer

Negating a statement

State in words the negation of the following sentence: For every martian M, if M is green, then M is tall and ticklish. I got the right answer to this, give or take a few words, but this is a question of form more than anything. After converting…
Snowman
  • 2,664
1
vote
2 answers

Resolution on set of clauses

Given this set of clauses: $\neg \phi = (\neg T \lor \neg Y)\land (S \lor \neg X ) \land (\neg X \lor Z \lor \neg Y) \land(X \lor T) \land (Y \lor U) \land (Y \lor \neg V)\land \neg S \land V$ I want to reach the empty set in order to prove a…
1
vote
1 answer

Is the True clause considered the proof of resolution refutation

So, basically I have the sentence $$ (P \Rightarrow (Q \Rightarrow R)) \Rightarrow ((P \Rightarrow Q) \Rightarrow (P \Rightarrow R))$$ and it was asked to prove it by resolution refutation. On the last step, I found three different clauses, all true…
1
vote
1 answer

Proposotional logic derivation

Show that (φ ∧ ψ) ↔ ¬(φ → ¬ψ) is derivable. I have derived ¬(φ → ¬ψ) from (φ ∧ ψ) by assuming (φ → ¬ψ) and (φ ∧ ψ) and deducing a contradiction. By cancellation of the hypotheses I can then conclude that (φ ∧ ψ) → ¬(φ → ¬ψ) is derivable, but I can't…
Craig
  • 11
1
vote
2 answers

Proving a simple assertion in Propositional Logic

I have to prove some Propositional Logic assertions. Given this one: $\alpha \models \beta \Leftrightarrow (\alpha \Rightarrow \beta)$ is valid Where $\models$ is entailment The answer is: $\alpha \Rightarrow \beta$ holds in those models where…
0
votes
1 answer

Properties that can be proven with induction on wff's?

Let $\mathcal{L_0}$ be the smallest set $L$ of finite sequences of $\textit{logical symbols}= \{(\enspace)\enspace\neg\to\}$ and $\textit{propositional symbols}=\{A_n\mid n\in\mathbb{N}\}$ for $n \in \mathbb{N}$ satisfying the following…
0
votes
1 answer

Can ECpqANpq get proved in intuitionistic logic?

I use Lukasiewicz/Polish notation. Given intuitionistic logic with the optional axioms for equivalence and negation given in the Wikipedia, can ECpqANpq or in other notation [(p$\rightarrow$q)=($\lnot$p$\lor$q)] get proved in intuitionistic logic?
0
votes
1 answer

Is there a simplifying algorith m for a formula in Disjunctive Normal Form?

Apologies if this question has been asked before. Please point me to it. I could not find it. Given a propositional formula which is Disjunctive Normal Form, is there an algorithm which outputs an equivalent formula which uses a minimal umber of…
Ishfaaq
  • 10,034
  • 2
  • 30
  • 57
0
votes
1 answer

How make equivalent transformations?

Please, help me make equivalent transformations with this formula (A∨C→B)(A→C)(¬B→¬A∧C)(¬A→(C→B))(B→¬C→¬A). Thanks.
Maxikkk
  • 11
0
votes
2 answers

Solving a contradiction in premises

I've got a set of premises: $m \rightarrow j, a \rightarrow j, \neg m \rightarrow a, a \rightarrow \neg j$ Clearly, $a \rightarrow \neg j$ Contradicts $a \rightarrow j$ I'm asked to proof that out of these premises follows the following…
Byebye
  • 277