Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

0
votes
1answer
9 views

Identifying ambiguities

I used lead and deadly as the ambiguities because they both can have different meaning. But I'm not sure how to explain how they can have different meaning in this sentence and how to restructure this ...
0
votes
2answers
10 views

Image e and preimage of a set using logical connectors

This might appear silly, I know that $$ \begin{array}{l} f(A) = \left\{f(x) : x \in A \right\} \\ f^{-1}(A) = \left\{x : f(x) \in A \right\} \end{array} $$ If $y\in f(A)$ is fixed can this be ...
0
votes
1answer
30 views

Proving $\exists k \in \mathbb{Z}: \forall l \in \mathbb{Z}: \lnot(k \mid l) $?

$$\exists k \in \mathbb{Z}: \forall l \in \mathbb{Z}: \lnot(k \mid l) $$ I have no idea how to approach this problem? If true, prove it, and if false prove the the negation. With its negation being: ...
1
vote
0answers
32 views

What is the “official” name for these boolean algebra rules?

In boolean algebra, we have the following simplification rules: $$P + (\ldots P \ldots) = P + (\ldots 0 \ldots)$$ and $$P \cdot (\ldots P \ldots) = P \cdot (\ldots 1 \ldots)$$ (Here $\;\ldots P \...
1
vote
4answers
50 views

Where does this rule for Boolean simplification come from?

In the simplification: $$\begin{align}A'BC + AB'C + ABC \\ BC(A' + A) + AB'C \\ BC + AB'C \\ \color{red}{C(B + AB')} \\ \color{blue}{C(B + A)} \\ AC + BC\end{align}$$ What is the rule that permits ...
-1
votes
1answer
17 views

Tautological Equivalence and Transitivity [on hold]

In propositional logic, let there be three sets of formulas $\Phi, \Phi', \Phi''$ such that $\Phi \Leftrightarrow \Phi'$ and $\Phi' \Leftrightarrow \Phi''$. Can transitivity be used here to deduce ...
0
votes
1answer
23 views

Proving associativity in propositional logic

$(p∧q) ∧ r ⊢ p ∧ (q∧r)$ In the sequent above, the only thing that happens is switching brackets between p&q and r, to q&r and separating out p. I could use the elimination rule between p&...
2
votes
1answer
50 views

Showing two sets of formulas are logically equivalent using induction.

Can someone let me know if my proof is okay for showing the following two sets are logically equivalent (in propositional logic)? I asked this a day or so ago but the post was very long, disorganized, ...
1
vote
2answers
43 views

Help writing the contradiction of this statement

I was given the statement and asked to write it out symbolically and negate it. "Given any integer $n>1$, there is a power of $2$ that is bigger than $n/2$ and less than or equal to $n.$" First, ...
2
votes
1answer
77 views

When does $(\square P \land \square Q) \to \square (P \land Q)$ hold?

If all axioms of classical propositional calculus hold and we work in modal logic that is at least K (ie. extremely weak), it is trivial to show $\square(P \land Q) \to (\square P \land \square Q)$. ...
3
votes
2answers
49 views

What is the correct formalization of the statement: “Zero is the only neutral element in respect to addition”

In my home work assignment I was asked to formalize different statements. One of them was (assuming that we are talking about whole numbers): "Zero is the only neutral element in respect to addition." ...
0
votes
1answer
22 views

Clarification on the formalization of tautological consequence

I have a mediocre question. Just to clarify, if a is a tautological consequence of b, then a ∨ b = b? It is assumed that a and b are literals.
2
votes
0answers
38 views

Prove that $\{ \phi \rightarrow(\psi \rightarrow \theta)\} \vdash \phi \wedge \psi \rightarrow \theta$?

Please, can you check is my solution of this problem $\{ \phi \rightarrow(\psi \rightarrow \theta)\} \vdash \phi \wedge \psi \rightarrow \theta$ good? First, I rewrote it like $\{ \phi \rightarrow(\...
34
votes
4answers
4k views

Why isn’t ‘because’ a logical connective in propositional logic?

In simple terms, could someone explain why there is not a logical connective for ‘because’ in propositional logic like there is for ‘and’ and ‘or’? Is this because the equivalent of ‘because’ is the ...
0
votes
0answers
36 views

$\neg (\neg A) \rightarrow A$ part of the axioms of propositional logic? [duplicate]

When talking with a mathematics teacher the other day, we discussed these axioms in the context of proving tautologies with semantic tableaux: $(p\to(q\to p))$ $((p\to(q\to r))\to((p\to q)\to(p\to r))...
1
vote
3answers
299 views

Logical equivalence of ¬p→q

Just wondering what other ways $\neg p \to q$ can be expressed. I know that $p\to q$ is logically equivalent to $\neg p\lor q$, hence I think that $\neg p\to q$ has the same logical equivalence as $p\...
0
votes
0answers
23 views

Show that a proposition using even number of instance of each variable and $\Leftrightarrow$ is a tautology.

I need to show that given a statement using an even number of each of the variables $X_1,X_2,...,X_{n}$ and bi-implication connective is always a tautology.
-2
votes
2answers
32 views

logic - how to convert this formula

I have this formula: $$(X \wedge (Y \rightarrow Z)) \vee \neg(\neg X \rightarrow (Y \rightarrow Z))$$ Is it possible to convert it to this: $$X ↔ (Y → Z)$$ the truth table show that they are ...
0
votes
1answer
37 views

Show that $ \{ (\phi \wedge \psi) \rightarrow \theta \} \vdash \phi \rightarrow(\psi \rightarrow \theta)$

How to show that $ \{ (\phi \wedge \psi) \rightarrow \theta \} \vdash \phi \rightarrow(\psi \rightarrow \theta)$? I tried to do it using deduction theorem and got $\vdash((\phi \wedge \psi) \...
2
votes
1answer
25 views

Notation of countable disjunction in infinitary logic

Let $L_{\omega_1}$ be a propositional infinitary language. The subscript $\omega_1$ in $L_{\omega_1}$ indicates that disjunctions and conjunctions of all lengths $<\omega_1$ are allowed. In other ...
-2
votes
1answer
23 views

Existence of total order for every set

please prove it from Compactness theorem for propositional logic. Don't assume AC in any form. I mean relation $<$ is total order for $X$ iff trichotomy transitivity irreflexivity are true about $...
0
votes
2answers
35 views

Proof for $\lor$ Elim: rule in Soundness Theorem

So far I have been told to assume the line is invalid and then arrive at a contradiction. Suppose the first invalid step derives the sentence $C$ by an application of $\lor$ Elim to the sentences $A\...
-1
votes
1answer
30 views

If $\Phi, \phi, \neg\psi$ is inconsistent, show that $\Phi \vdash \phi \to \psi$.

If $\Phi, \phi, \neg\psi$ is inconsistent, show that $\Phi \vdash \phi \to \psi$. What I have so far: If $\Phi, \phi, \neg\psi$ is inconsistent, then $\Phi, \phi \vdash \psi$. Then by deduction, $\...
1
vote
1answer
32 views

Finding a countable, independent, and equivalent set.

For countable consistent set of well-formed formulas $\Phi$, I have to find a set $\Psi$ that is not necessarily a subset of $\Phi$ that is countable, independent, and equivalent to $\Phi$. My idea ...
0
votes
0answers
13 views

Implication used in boolean condition

Sorry if this is a basic problem. Is the following true: $(p \rightarrow q) \land p \land r \vDash q \land r$? A little more detail, I am trying to determine the following: if $p \rightarrow q$ ...
0
votes
1answer
49 views

If both $\Phi, \neg\phi$ and $\Phi, \psi$ are inconsistent, then $\Phi \vdash \neg(\phi \to \psi)$.

Could someone check whether my solution is okay? If both $\Phi, \neg\phi$ and $\Phi, \psi$ are inconsistent, then $\Phi \vdash \neg(\phi \to \psi)$.
0
votes
3answers
60 views

What's the error in my proof of the statement: The product of two irrational numbers is irrational?

Statement: The product of any two irrational numbers is irrational. Formally it can be written as: $$\Big(\forall x \forall y\Big)\,\Big(\big(x \notin \mathbb{Q} \wedge y \notin \mathbb{Q}\big) \to \...
0
votes
3answers
31 views

Why is $ (a \lor b \lor c) \oplus ( a \lor b)$ equivalent to $\lnot a \land \lnot b \land c$?

I'm having a hard time understanding why $(a \lor b \lor c) \oplus (a \lor b)$ (where $\oplus$ stands for XOR) is equivalent to $\lnot a \land \lnot b \land c$ in propositional logic. Any help would ...
1
vote
2answers
48 views

If $\Phi \vdash \phi \to \psi$, show that $\Phi, \phi, \neg\psi$ is inconsistent.

If $\Phi \vdash \phi \to \psi$, show that $\Phi, \phi, \neg\psi$ is inconsistent. I am stuck on my proof. Assume that $\Phi \vdash \phi \to \psi$. Then $\Phi, \neg(\phi \to \psi)$ is inconsistent ...
1
vote
1answer
27 views

Proving any propositional formula can be written a certain way

How do I start with this? I know that there are $2^4$ different possible truth tables for $P$ but i'm not sure where to go from there.
1
vote
3answers
57 views

Compactness Theorem for Propositional Logic

Here is the compactness theorem: If every finite subset of $\Phi$ is satisfiable, then $\Phi$ is satisfiable. Is the contrapositive the following? If $\Phi$ is unsatisfiable (tautologically ...
3
votes
3answers
57 views

What is meant by the 'truth' of a statement in a truth table? [duplicate]

The focus of propositional logic is said to be argument schemas that lead to valid conclusions, and not with the contents of the arguments themselves. This implies that an argument can consist of ...
0
votes
1answer
42 views

Searching for a reference book in logic [closed]

I am attending a mathematical logic course and I need one or more books to be my references. The professor did not suggest any book in particulare and this is why I am writing here. The topics of the ...
1
vote
1answer
37 views

How to denote “It is not true that A but not B” in symbolic logic form? [closed]

I want to ask a question about logic and proposition calculus. Let p be "Mary visits America", let q be "Mary visits France", and let r be "Mary visits China". Write "It is not true that Mary ...
1
vote
1answer
60 views

Intuitionistic logic and derivation

It is my first approach to intuitionistic logic (IL) and, even if I understand the principle behind it, I struggle understanding when a sequent is derivable in IL and when is not. I know that IL ...
0
votes
1answer
26 views

How to use distribution with propositional logic?

I need to apply the distribution rule for propositional logic. I know that the if you have a sentence like $A ∧ (B ∨ C)$ then applying distribution would result in the sentence $(A ∧ B) ∨ (A ∧ C)$. I'...
-2
votes
0answers
25 views

If we have the statement A or B is it still true if A and B is false?

A partial Order is a relation that suffices the following properties: i) for every (a,b) element of R c (M x M) there is only one relation a < b or a=b or a > b ii) a < b and b < c -> a &...
1
vote
0answers
24 views

Compact witness of satisfiability of a formula in intuitionistic logic

Given a formula in intuitionistic sentential logic, there is a nice, compact textual representation for a witness of its tautology, namely a program in a typed lambda calculus with introduction and ...
2
votes
1answer
29 views

Let $f(x_1, x_2)$ be a term in a first order language $L$; call this term $t$. Decide if $t$ is free for $x_1$ in the following formula of $L$

Definition: $\varphi$ a formula, $t$ a term. We say "$t$ is free for $x_i$ in $\varphi$ if no free occurence of $x_i$ in $\varphi$ lies within the scope of $\forall x_j$ where $x_j$ is a variable ...
0
votes
1answer
40 views

Is ~p -> ~q an acceptable conditional statement?

I have a conditional statement that was posted in a chat room that I am trying to parse. I'm going to edit a little to make the question more concise. The statement is: "No taxation without ...
1
vote
1answer
18 views

Existence of a finite almost-non-contradicting triple

Define an n-variable propositional formula as a function $f: \lbrace{0,1 \rbrace}^n \rightarrow \lbrace 0,1 \rbrace$. A function $f$ is a contradiction if it maps all it's inputs to false ($0$ in this ...
-1
votes
1answer
61 views

Help with natural deduction system (Propositional logic) [closed]

In natural deduction, I'm trying to get to $(A \to B) \land (\lnot A \to C)$ from the following formula: $(A \land B) \lor (\lnot A \land C)$ and vice-versa, i.e. $(A \land B) \lor (¬ A \land C) \...
0
votes
1answer
42 views

Deduction of Modus Tollens

I was wondering what is a deduction of Modus Tollens is. However, there are only 3 axioms that I can use to proceed on the deduction. The 3 axioms are in the link.
0
votes
0answers
46 views

$Γ \models α $if and only if $Γ ∪ \{(¬α)\}$ is not satisfiable. [duplicate]

Let $\Gamma$ be some set of well formed formulas and let $\alpha \in \mathrm{WFF}$. Prove the following statement: $\Gamma \models \alpha$ if and only if $\Gamma \cup \{(\lnot\alpha)\}$ is not ...
0
votes
2answers
33 views

Modulo/Congruent theorem into symbolic/predicate notation

For a positive integer $n$, two numbers $a$ and $b$ are said to be congruent modulo n, if $(a-b)$ is some integer multiple of $n$, or mathematically: $\hspace{15em} a=kn+b$ I am assuming that ...
1
vote
1answer
42 views

In logic, what does it mean when it says “$\Phi, \phi, \neg\psi$ is inconsistent”?

Does it mean $\Phi, \phi$ is inconsistent and $\Phi,\neg\psi$ are inconsistent?
2
votes
1answer
61 views

Proving that $\{P_1,P_2, \dots, P_n\}$ is complete but not maximally consistent

Prove that $\{P_0,P_1, \dots, P_n\}$ is complete but not maximally consistent So I need to prove that this is complete, consistent, but not maximally consistent. But I have a few confusions about ...
1
vote
2answers
70 views

Logical system: proving sentence is not deductible

Note: This is a part of my homework. I have an formal system L(↑,↓,→) with Modus ponens and following three axioms: ↑↑↓↓φ (↑↓φ → ↑ψ) ((φ→ψ)→(↑ψ→↑φ)) And I need to decide, if it's possible to derive ...
1
vote
2answers
37 views

It it possible to express an always-true function using product of sums in boolean algebra?

Consider such boolean function: $$f(x,y,z) = 1$$ It is easy, but a trifle tedious, to express this function using the sum of products. However, let's say that we are asked to express it using the ...
1
vote
1answer
53 views

First-order logic validity question

I'm a beginner learning first-order logic and I have a couple of difficulties understanding the following question: "Let L be a first order language with just one predicate, =, and no constants or ...