Stack Exchange Network

Stack Exchange network consists of 175 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 [formal-systems]

A formal system is broadly defined as any well-defined system of abstract thought based on the model of mathematics. (Def: http://en.m.wikipedia.org/wiki/Formal_system)

27
votes
9answers
3k views

Is formal truth in mathematical logic a generalization of everyday, intuitive truth?

I'm trying to wrap my head around the relationship between truth in formal logic, as the value a formal expression can take on, as opposed to commonplace notions of truth. Personal background: When I ...
0
votes
3answers
212 views

Are axioms assumed to be true in a formal system?

In a logical system, there is assignment of truth values to the sentences in the language, and axioms are assigned the true value. A logical system is a formal system. In a formal system, there is ...
3
votes
4answers
1k views

natural deduction: introduction of universal quantifier and elimination of existential quantifier explained

Currently, I am dealing with the calculus of natural deduction by Gentzen. This calculus gives us rules to manipulate so-called sequents. Definition. If $\phi_1,\dots, \phi_n,\phi$ are formulas, then ...
8
votes
4answers
400 views

Calculus of Natural Deduction That Works for Empty Structures

Currently, I am dealing with the calculus of natural deduction by Gentzen. This calculus gives us rules to manipulate so-called sequents. Definition. If $\Gamma$ is a set of formulas and $\phi$ a ...
14
votes
1answer
4k views

Formal System and Formal Logical System

I was reading the Wikipedia article for Mathematical_logic. When reaching Formal_logical_systems, I was curious about its definition and clicked into its own article Logical_system, which redirected ...
5
votes
3answers
567 views

Aftermath of the incompletness theorem proof

This is somewhat of a minor point about the incompletness theorem, but I'm always a little unsure: So one proves that there is a formula which is unprovable in the theory of consideration. Okay, at ...
2
votes
1answer
300 views

Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1] Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...
0
votes
2answers
200 views

Does a formal system having inference rules imply that it is a logic system?

From Wikipedia Formal systems in mathematics consist of the following elements: A finite set of symbols (i.e. the alphabet), that can be used for constructing formulas (i.e. finite ...
9
votes
3answers
2k views

Why is establishing absolute consistency of ZFC impossible?

Why is establishing the absolute consistency of ZFC impossible? What are the fundamental limitations that prohibit us with coming up with a proof? EDIT: This post seems to make the most sense. In ...
9
votes
5answers
2k views

Resources for learning formal math?

I'd like to learn formal math. Preferably, though not necessarily, starting with predicate logic/first order logic rather than higher order logic. I am trying to find resources (papers, books etc.) ...
10
votes
0answers
209 views

Is it possible to formalize all mathematics in terms of ordinals only?

Our experience shows that all finitary mathematical objects could be encoded using the natural numbers, and all operations on those objects could be expressed in terms of a few basic operations on ...
3
votes
3answers
374 views

Foundation of Formal Logic

All the books that I’ve read about formal logic either starts assuming the existence of set theory (they talk of countable sets of symbols and define formulae as sequences of symbols), or follow an ...
13
votes
4answers
21k views

What makes a context free grammar ambiguous?

What makes a context free grammar ambiguous?
5
votes
2answers
544 views

Are there formal systems that are not logical systems?

From WIkipedia A logical system or, for short, logic, is a formal system together with a form of semantics, usually in the form of model-theoretic interpretation, which assigns truth values to ...
5
votes
3answers
789 views

Why can't we use memoization to parse unambiguous context-free grammars in linear time?

This is a follow-up question to Why is it hard to parse unambiguous context-free grammar in linear time? I know that Parsing Expression Grammars (PEG) can be parsed in linear time using a packrat ...
5
votes
5answers
780 views

Can a polynomial size CFG over large alphabet describe a language, where each terminal appears even number of times?

Can a CFG over large alphabet describe a language, where each terminal appears even number of times? If yes, would the Chomsky Normal Form be polynomial in |Σ| ? EDIT: What about a language where ...
2
votes
1answer
563 views

Difference between Hilbert's program and Russell & Whitehead's Principia Mathematica

Can someone explain to me the difference between Hilbert's program and Russell & Whitehead's Principia Mathematica? I know both of them wanted to reduce the mathematics into a set of axioms and ...
2
votes
2answers
816 views

Why is it hard to parse unambiguous context-free grammar in linear time?

From this question, I gather that whether unambiguous CF grammar can be parsed in linear time is an open problem. I'd like to know what the major roadblocks to achieve this are. That is, what made the ...
3
votes
1answer
62 views

Codification of a formal language in set theory.

Starting with an arbitrary class of sets $\Gamma$, can you generate a free semigroup $\Gamma^*$ over $\Gamma$ with the group operation of concatenation ($\frown$)? The goal here is to codify a formal ...
0
votes
1answer
49 views

Can the Negation of a Conditional Implying the First Atomic Proposition Get Proven in Around 50 Steps?

The following uses Polish notation with the following definition for meaningful expressions. All lower case letters are meaningful expressions. If $\alpha$ is a meaningful expression, then so is N$\...
-1
votes
2answers
706 views

Definition of the bound and unbound variable [closed]

What do we mean by bound and unbound variable? I have difficulty to understand their meanings, Could anyone help me with that?
3
votes
1answer
154 views

What is the minimal axiomatization of a set of structures?

I wonder what the minimal axiomatization of a set of structures mean? I came across this term from Wikipedia: For a theory $T\in A,$ let $F(T)$ be the set of all structures that satisfy the ...
2
votes
1answer
1k views

Generating all words in a language from CFG

I have a non-ambiguous context-free grammar. Is there some standard algorithm to create list of all the words in the language the CFG defines? This can be done with an abvious brute-force search by ...
0
votes
1answer
366 views

What are the differences between a collation and a rule of formation?

I'm a beginner in mathematical logic, and currently studying(myself, without any colleague, which is sad and so asking in here) basics of formal system. Before asking a question, I'll introduce my ...
0
votes
2answers
197 views

How to use axioms to prove a derivation in propositional calculus?

Given a formal system called "$P0$" that has 1 rule (Modus Ponens) and 3 axioms: $1.$ $\alpha$ $\rightarrow$$(\beta \rightarrow \alpha)$ --- (Ak) $2.$ $(\alpha \rightarrow (\beta \...
-2
votes
3answers
164 views

equality – just a relation between *two* objects? [closed]

I just read the wikipedia article about "equality". Why do they treat equality = as a relation linking just two objects? It seems like they are treating = just as a symbol (which can be written ...