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).

Filter by
Sorted by
Tagged with
1 vote
0 answers
34 views

Showing Euclid's Proposition 30 ("Lines parallel to the same line are parallel to each other") is equivalent to the 5th Postulate.

I am trying to show that the 30th Euclid's proposition, "Straight lines parallel to the same straight line are also parallel to one another." is equivalent to the 5th Postulate: "If ...
user avatar
0 votes
3 answers
63 views

$A$ says "I am a knight" and $B$ says "$A$ is a Knave?" therefore what is $A$ and $B$?

$A$ says "I am a knight" and $B$ says "$A$ is a Knave?" therefore what is $A$ and $B$ ? The logic is Knights always tell the truth and Knaves always lie. What I'm thinking is ...
user avatar
  • 1,340
-5 votes
0 answers
56 views

How do I translate the following sentences from English to predicate logic? [closed]

The thief is only liable if they saw him enter the tunnel and found the stolen item in his possession. If witnesses see him enter the tunnel and the stolen object is not found in his possession, then ...
user avatar
0 votes
1 answer
46 views

Does Every Axiom Set For Classical Propositional Calculus Have Two Negations, and If So, Why?

Every axiom set for classical propositional calculus (under uniform substitution and detachment) with a conditional and negation connective that I've seen has at least two negation symbols in it (and ...
user avatar
1 vote
0 answers
49 views

Can circuit $f'$ replace circuit $f$?

Assume Peter and Paul develop a circuit. Paul tries to convince Peter that $f$ may be replaced by $f'$ to save hardware resources. $$\begin{aligned} f &:= \neg x_0 \land \neg x_1 \land \neg x_2 \...
user avatar
0 votes
0 answers
13 views

Generalized formula that will result in CNF when expanded

Consider we have 4 propositional atoms $a, b, c, d$ and have the following formula: $$ \phi_1 = (a_1 \vee b_1) \wedge (c_1 \vee d_1)$$ $$ \phi_2 = (a_2 \vee b_2) \wedge (c_2 \vee d_2)$$ $$ ... $$ $$ \...
user avatar
0 votes
0 answers
10 views

Czelakowski matrix semantics vs ordinary matrix semantics vs Co-Czelakowski matrix semantics

The kind of matrix semantics that I'm accustomed to seeing is something like $\langle A, F \rangle$ where $A$ is an algebra in some signature and $F$ is a subset of the carrier of $A$. A Czelakowski ...
user avatar
  • 6,426
-1 votes
0 answers
27 views

Prove that ⊢(¬p→q)→(¬(¬q→s)→p) [closed]

First I checked that the formula is a Tautology then I used the deduction theorem : so we only need to prove that : {(¬p→q),¬(¬q→s)}⊢p. I tried proving it using DS but failed , can someone help ?
user avatar
0 votes
1 answer
28 views

Need help constructing a proof tree (or truth tree) for the following argument symbolized in predicate logic.

For context, I am a logic simpleton studying for an exam in a graduate-level introduction to symbolic logic. One of the techniques I'm expected to know is constructing proof trees to test the validity ...
user avatar
  • 55
0 votes
1 answer
40 views

Definition of a protoalgebraic deductive system

I'm trying to understand the definition of a protoalgebraic logic given in Blok and Pigozzi. I'm specifically interested in two things: Exactly which family of Leibniz operators the authors are ...
user avatar
  • 6,426
0 votes
0 answers
19 views

Proof of the Local Deduction Theorem, for one of many logics

(I also asked this in MathOverflow) I'm looking for a proof of the Local Deduction Theorem for any one of many logics. That is, a proof of the statement: $\Sigma \bigcup \{\phi\} \models \psi$ iff for ...
user avatar
  • 149
0 votes
1 answer
24 views

An exercise in fuzzy logics built from a t-norm

(I also asked this in MathOverflow) Consider the following t-norm: $ a * b = \begin{cases} \text{$2ab,$} &\quad\text{if $a, b$}\le1/2\\ \text{$min\{a, b\}$} &\quad\text{...
user avatar
  • 149
2 votes
3 answers
50 views

Predicate logic: Symbolize this categorical statement.

I am a logic neophyte and simpleton studying for an exam in a graduate-level course in elementary symbolic logic. I am trying to symbolize the following categorical statement: "No artist is a ...
user avatar
  • 55
-1 votes
2 answers
126 views

In logic, does $A\wedge B$ mean the same as $B\wedge A$. Is it provable? [closed]

In logic, does $A\wedge B$ mean the same as $B\wedge A$. Is it provable?
user avatar
  • 7
1 vote
1 answer
45 views

A language $\mathcal{L}$ with $n$ atomic propositions can express $2^{2^n}$ non-equivalent propositions

I tried to prove the statement and wasn't sure if it is correct. Theorem A language $\mathcal{L}$ with $n$ atomic propositions can express $2^{2^n}$ non-equivalent propositions. Proof Two propositions ...
user avatar
  • 57
1 vote
0 answers
14 views

Conjunctive Normal Form (CNF) of a generalized formula

Given a propositional logic formula of: $$ \phi_1 = (a \wedge b) \vee (a \wedge c) \vee (a \wedge d) \vee (b \wedge c) \vee (b \wedge d) \vee (c \wedge d) $$ Where the CNF of the given formula is: $$...
user avatar
0 votes
0 answers
14 views

Represent 3-valued logic with 2-valued logic? Or a 3-valued expert system

Can you represent a 3-valued logic with 2-valued logic? I was looking for a 3-valued Expert System where a statement can have one of three values: True, False, Unknown. But I failed to find one. So I ...
user avatar
4 votes
2 answers
126 views

Prove that is is not possible to define the connective $\land$ in terms of $\lnot$ and ↔

[Exercise 12.2] Prove that is is not possible to define the connective $\land$ in terms of $\lnot$ and ↔. Suggestion: By induction on the complexity of formulae constructed by these ...
user avatar
3 votes
2 answers
152 views

Are there different kinds of invalid arguments?

in my semantics class we had two examples of invalid arguments: $$\begin{array}{rl} & p \lor q \\ & \neg p \\ \hline \therefore & \neg q \end{array}$$ and $$\begin{array}{...
user avatar
  • 77
1 vote
1 answer
36 views

Propositional Logic, proving that the sequent of every valid argument can be proved

I am studying a from "A First Course in Logic" by Mark V. Lawson. I am currently on the first chapter which covers propositional logic. The author has just introduced Sequential Calculus and ...
user avatar
0 votes
1 answer
33 views

At most $k$ contiguous $\mbox{true}$ values in a Boolean array using SAT

Given an integer $k > 0$ and a Boolean array $A$ of length $n$, find a simplified and efficient CNF formula to ensure that there is not more than $k$ contiguous $\mbox{true}$ values in this array. ...
user avatar
  • 1,242
-2 votes
0 answers
40 views

Prove the validity of p → q, s → t ⊢ p ∨ s → q ∧ t

I'm fairly new to logic and I was wondering if anyone could help me with the proving the validity of this sequent: p → q, s → t ⊢ p ∨ s → q ∧ t This is an exercise from the logic in computer science ...
user avatar
0 votes
0 answers
60 views

Proving that (α → β) ⊢ (α → ¬¬β) in Propositional Calculus

Let $L$0 = $L$ [{¬, →}]. Define the system $L$0 as follows: An axiom of $L$0 is any formula of $L$0 of the form (A1) $(α → (β → α))$ (A2) $((α → (β → γ) → ((α→β) → (β→γ)))$ (A3) $((¬β → ¬α) → (α → β))...
user avatar
  • 29
2 votes
0 answers
116 views

The Schröder–Bernstein theorem via the Compactness Theorem for propositional logic

The Schröder–Bernstein theorem states that if for two sets $A$ and $B$ there exist injective functions $f:A\rightarrow B$ and $g:B\rightarrow A$ then there exists a bijective function $h:A\rightarrow ...
user avatar
  • 2,962
2 votes
1 answer
98 views

Tychonoff's Theorem via the Compactness Theorem for propositional logic

I am trying to prove Thychonoff's Theorem using the Compactness Theorem for propositional logic. A space $X$ is compact if and only if every collection $C$ of closed subsets of $X$ having the finite ...
user avatar
  • 2,962
0 votes
1 answer
92 views

How to Prove the these claims in Propositional Logic?

This Question included multiple sub-questions, I removed those I solved and posted only those I failed (they aren't related). $\Sigma$ is called special if for each $\alpha, \beta$ in $WFF$: $\Sigma \...
user avatar
  • 139
0 votes
0 answers
42 views

How to prove (P v Q) ┠ ¬( ¬P & ¬Q) with limited Rules?

I come here in time of need, as due to the plague, I was unable to attend a lesson, but need to complete the following task: Prove the following with only MTP(Modus tollendo ponens) and the ...
user avatar
1 vote
1 answer
92 views

Proof by contradiction to show irrationality of $\sqrt{2}$ logically

I am trying to learn more about basic logic in order to make my proofs and reasoning more precise or even "mechanical". Just to make sure that my proof really shows what I wanted. (Any ...
user avatar
2 votes
1 answer
143 views

Using the Compactness Theorem for Propositional Logic to prove that the countable union of countable sets is countable

Consider a disjoint family $\{A_{n}\}_{n\in\mathbb{N}}$ of countable sets, let $A$ denote the their union. We can define a language $L$ to have atoms $p_{an}$ for each $a\in A$ and $n\in\mathbb{N}$ (...
user avatar
  • 2,962
0 votes
0 answers
32 views

Proof of Completeness Theorem in Enderton's Logic, satisfiability of Γ∪Θ∪Λ

I have similar question with this post Proof of Completeness Theorem in Enderton's Logic, satisfiability of Γ∪Θ∪Λ, so I quote some of his/her description: I'm reading the proof of the Completeness ...
user avatar
  • 1
2 votes
1 answer
38 views

Question About The Validity of An Argument

I have been reading and doing exercises form the book How to Prove It: A Structured Approach until I have reached section 1.2. I have come across the definition of a valid argument: An argument is a ...
user avatar
  • 373
3 votes
2 answers
89 views

A natural deduction proof of $\neg (A \leftrightarrow \neg A ) $.

I want to prove $\neg (A \leftrightarrow \neg A ) $ in natural deduction: I tried first But I can't figure how to discharge the hypothesis $A$ and $\neg A$. I then tried Here I just need to ...
user avatar
  • 4,666
2 votes
0 answers
57 views

Proving a tautology by using logical equivalences

I have to prove $$(\lnot(a\land b) \land (b \lor c)\land(c\rightarrow d)) \Rightarrow (a \rightarrow d)$$ So far I have done this: $$\lnot (a\land b)\land (b\lor c)\land (c\rightarrow d)$$ $$\iff (\...
user avatar
0 votes
0 answers
45 views

A natural deduction proof of $\neg (A \wedge B) \rightarrow (A \rightarrow \neg B)$ without RAA

I am doing (for fun) the exercices of this lean tutorial. For the third exercice of section 3.6. Exercises: "Give a natural deduction proof of $\neg (A \wedge B) \rightarrow (A \rightarrow \neg ...
user avatar
  • 4,666
0 votes
0 answers
49 views

Is the "parallel axiom" sentence, a proposition in absolute geometry?

I will try to explain in other words. Given a formal theory of absolute geometry, we are able to write the expression whose meaning is the paralel axiom. The question is, that expression is a "...
user avatar
  • 166
1 vote
0 answers
79 views

Is it correct to judiciously construct a quantifier tableau to yield a desired falsification of a formula, yet the rules to apply weren't exhausted?

I am a beginner in logic, which I am learning on my own. I am aware of the fact that a quantifier tableau with open branches doesn’t always show the formula under consideration is falsified- unless ...
user avatar
  • 2,962
0 votes
2 answers
81 views

New Proof System

I've been going on past homework and I've faced a question that seems a little bit illogical to me or that it's too simple. Here is the question: Question: Let N be a new semantic proof system which ...
user avatar
6 votes
1 answer
117 views

Proving (disproving?) a statement when its condition is not satisfied

Consider the following implication. Let $k\in \mathbb{Z}$. If $k^{2} + 5k$ is odd, then $k^{2}+5k+1$ is odd. At first it seems to be false, and one could proceed easily to prove it false directly by ...
user avatar
  • 115
0 votes
1 answer
48 views

How can I show that $ \{A \to B, B \to C \} \vdash A \to C $ without using deduction theorem in hilbert-style system?? [duplicate]

I've been confused with that for a few days. The axiomatic system is: α→(β→α) α→(β→γ)→((α→β)→(α→γ)) (¬β→¬α)→(α→β)
user avatar
1 vote
0 answers
26 views

Completeness of n-(finitely)-Valued Gödel Logic w.r.t IPC+Linearity+$F_n$

n-Valued Gödel Logic is apparently complete with respect to IPC with the added axioms of Linearity: $(A \rightarrow B) \lor (B \rightarrow A)$ and $F_n$: $\bigvee_{1 \leq i < j \leq n} (A_i \...
user avatar
  • 91
0 votes
1 answer
67 views

How to prove that $P_b \leftrightarrow (P_a \land P_b), P_a \leftrightarrow \neg P_b \vdash P_a$ with natural deduction

I need to build a proof for $P_b \leftrightarrow (P_a \land P_b), P_a \leftrightarrow \neg P_b \vdash P_a$ with natural deduction... I have built the following proof, however I am stuck in the middle ...
user avatar
1 vote
1 answer
47 views

Propositional Interpolation Theorem

In Fundamentals of Mathematical Logic by Hinman, page 40, there is the following exercise, rewritten in my own notation: Let $S$ be the set of all propositions. For $\phi \in S$, let $P_\phi$ be the ...
user avatar
  • 929
0 votes
0 answers
16 views

Finitely Valued Multi-Valued Logic only has finitely many strengthening

I was reading Kurt Gödel Collected Works by Feferman, and in the introductory note to Godel's 1932 paper A.S. Troelstra states that ''it is not difficult to show that any propositional logic ...
user avatar
  • 91
1 vote
0 answers
65 views

Using the Calculus of Constructions as a metalogic

Usually the Calculus of Construction is used via the Curry-Howard isomorphism, which makes it equivalent to intuitionistic first order logic. But what I am interested in is to use CoC as a metalogic ...
user avatar
0 votes
1 answer
35 views

What does it mean for propositions to be in parenthesis without logical operators.

i have stumbled upon this on one of my schools automatized tests. In my universities discrete math 1 module: "Let P and Q be logic expressions, applying the laws of calculus prove the following:&...
user avatar
  • 3
3 votes
0 answers
65 views

Where's the difference between $\vDash$ and $\Rightarrow$? [duplicate]

I'm sorry if that question has already been asked. Sometimes in propositional logic when proving "$\phi \rightarrow \psi$ is a tautology" using truth tables people write $\psi \Rightarrow \...
user avatar
  • 77
0 votes
0 answers
24 views

Converting First-Order Logic to CNF

I am having a lot of trouble using the rules of converting First-Order Logic to CNF. I have this statement: ∀x∃y : ([P(x, y) → Q(y, x)] ∧ [Q(y, x) → S(x, y)]) → ∃x∀y : [P(x, y) → S(x, y)] After ...
user avatar
0 votes
1 answer
44 views

Is $(A \land B)$ a form of $(p \land p)$?

This question is related to my previous question on forms of statements, here: Rigorous definition of the set of forms of a propositional formula. Consider the propositional formula $(p \land p)$, ...
user avatar
  • 13.3k
1 vote
2 answers
84 views

Missteps in deriving a conclusion from premises

The problem is to show that $q \rightarrow r$ is a conclusion of the premises $$(p\wedge t) \rightarrow (r \vee s),\\q \rightarrow (u \wedge t),\\u \rightarrow p,\\\neg s.$$ Why is the following ...
user avatar
1 vote
1 answer
58 views

Logic: Same premises and different conclusion?

Suppose that there are $n$ premises, say $p_1,\cdots, p_n$. Then, is it possible to obtain two different conclusion? That is, Can we obtain two conclusions $q_1$ and $q_2$ using the rule of inferences ...
user avatar

1
2 3 4 5
101